[DP] BJ_2775, 부녀회장이 될테야

[문제의 접근] 

 이 문제에서의 핵심은 바로 다음 글귀이다. "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다." 이 것을 읽고 어떤 생각을 해야할까? 특이한 조건이네 이렇게? 특이한 조건인건 맞다. ㅎㅎ. 많은 알고리즘 문제에서는 스토리를 만들어내기 위해 사실 별로 필요없는 문구들도 많이 넣기는 하는데, 위의 문구를 보면 아래와 같은 수식을 떠올려야 한다. 우리는 알고리즘 문제를 풀고 있고 알고리즘은 수식으로 이루어지니 말이다. 

arr[a][b] = arr[a-1][1] + arr[a-1][2] + ... arr[a-1][b]

 

 그럼 이 문제를 위의 수식 그대로 풀어내면 될까? test case의 T의 숫자가 주어지지 않아서 명확하진 않지만, k와 n이 크지 않으니 그런 방법도 가능할 수도 있을 것 같다. 그런데 그보다 더 smart한 방법이 있다. 매번 위의 공식대로 구하는 대신에 미리 위의 각 층, 각 호 마다 사는 사람의 수를 구해서 저장해 두고 실제로 필요할 때마다 꺼내 쓰는 방법이다. 그러면 아래와 같은 공식이 가능해 진다. 

arr[a][b] = arr[a][b-1] + arr[a-1][b]
// a층 b호에 사는 사람수 = a층 b-1호에 사는 사람수 + a-1층 b호에 사는 사람 수
arr[a][b] = arr[a-1][1] + arr[a-1][2] + ... arr[a-1][b]
// 아래 수식 보다 위의 수식이 계산량이 훨씬 적다.

 

  알고리즘에서는 계산량을 줄이는 것이 핵심이니 위의 수식을 사용하는 것이 훨씬 유리할 것 같고, 위의 수식 처럼 이미 구해놓은 이전의 문제(이전 부분의 문제)에서 다음의 문제(다음 부분 문제)를 계산해 낼 수 있는 것을 점화식이라고 한다. 이렇게 점화식을 세워 놓으면 문제 해결은 쉬워진다. 점화식을 구하는게 어려울 뿐이므로..

[Dynamic Programming]

 동적 계획법(Dynamic Programming)에는 기본적인 조건이 필수적으로 만족해야 한다. 보통 크게 2가지 조건을 만족해야 한다고 이야기 한다. 

1. Overlapping Subproblem, 부분 반복문제라고 해석하는데 똑같은 계산을 반복적으로 해야하는 경우에 동적계획법(Dynamic programming)을 적용하는 것이 효과적이다. 동적계획법이 이러한 반복적인 계산을 줄일 수 있게 해주기 때문이다. 
2. Optimal Substructure, 최적 부분 구조라고 해석하며 작은 문제에서 구한 최적의 답을 바탕으로 합쳐져서 큰 문제의 최적해를 구해낼 수 있어야 한다는 것이다. 

 부분 반복 문제와 최적 부분 구조가 나타나야 위의 점화식이 도출된다고 보면 될 것 같다.  동적 계획법으로 코드를 작성해 보자. 0층 초기값을 설정하고, 점화식을 전개해서 답을 dp 배열에 저장해 두고, 각 층, 호에 해당하는 dp 배열에서 값을 불러와서 최종 값 배열에 저장하는 형식을 가지고 있다. 

<C++>

void solve() {
    for (int i=1;i<15;i++) {
        dp[0][i] = i; // 0층 초기값 설정 
    }

    for (int i=1;i<15;i++) {
        for (int j=1;j<15;j++) {
            dp[i][j] = dp[i][j-1]+dp[i-1][j]; // 점화식 전개
        }
    }

    for (int i=0;i<t;i++) {
        sol.push_back(dp[k[i]][n[i]]); // inquery
    }
}

 

<Python>

def solve():
    dp = [[0]*15 for _ in range(15)]
    sol = []
    for i in range(1, 15): # 0층 초기값 설정
        dp[0][i] = i
    
    for i in range(1, 15): # 1층부터
        for j in range(1, 15): # 1호부터
            dp[i][j] = dp[i][j-1] + dp[i-1][j] # 점화식 전개
    
    for i in range(t): # 저장된 dp 배열에서 층, 호의 값을 호출
        sol.append(dp[flr[i]][room[i]])
    return sol

최종적인 해답은 solution 이 저장되어 있는 sol 배열에서 값을 하나씩 화면에 출력해 주면 모든 풀이 과정이 종료된다.

<Python Code> https://github.com/Koo82/Algotirhm/blob/main/%5BDP%5DBJ_2775.cpp

<C++ Code> https://github.com/Koo82/Algotirhm/blob/main/%5BDP%5DBJ_2775.cpp