BOJ. 2775

#BOJ2775

부녀회장이 될테야

드디어 무언가 문제다운 문제를 소개할 수 있게 된 것 같다. 이 문제는 기본적으로 DP(Dynamic Programming)을 사용해서 해결하는 문제이다. 이게 영어로 해놓으니깐 조금 멋있어 보이는데 그냥 재귀랑 매우 유사하다. 간단한 아이디어 하나로 작은 부분의 문제를 해결하는 과정을 반복해서 큰 문제를 해결하는 알고리즘 방법 중 하나이다. DP를 사용하는 문제들이 대체로 아이디어 발상 과정이 어렵지 막상 구현은 쉽다. 이 문제도 마찬가지인데 1층의 N호에 거주하고 있는 사람들은 기본적으로 1부터 N까지의 합의 사람 수만큼 살고 있으면 된다. 하지만 이후에 2층 3층으로 올라가면 올라갈수록 더하는 과정이 복잡하고 그렇기 때문에 이 문제를 해결하기 위해서는 차근차근 1층N호까지 다 구해서 구하고자 하는 층수의 N호까지 쭉 올라가면 된다. 이를 코드로 구현하면 다음과 같다.

# include "iostream"
using namespace std;

int main(void){
   int T = 0;
   cin >> T;
   for(int i = 0; i < T; i ++){
       int k, n, ans[n];
       cin >> k >> n;
       for (int j = 1; j <= n; j++){
           ans[j - 1] = j - 1;
       }//기본 케이스를 만들어주는 과정
       for (int j = 0; j < k; j++){
           for (int ii = 1; ii < n; ii++){
               ans[ii] += ans[ii - 1];
           }
       }//아래부터 위로 쭉 올라가는 과정
       cout << ans[n - 1];
   }
}

솔직히 풀이 과정 자체만 보면 간단한데 실제적으로 내가 이걸 처음부터 어떻게 가고 하는 과정을 찾는건 생각만큼 쉽지 않다. 특히 구현하는 과정에서 파이썬과 다르게 직관적이지 않다고 해야하나 그래서 오류가 상당히 많이 나와서 화가 많이 났다. 크리스마스 이브에 이런걸 하고 있는 나 자신을 보자니 자괴감이 든다...와 뭐지? 제출할 때 당연히 맞을 줄 알고 위풍당당하게 올렸는데 틀렸습니다가 50%에서 뜨네... 와 문제를 해결했는데 endl을 안해서 그랬던 거였다... 너무 억울하다...

# include "iostream"
using namespace std;

int main(void){
    int T = 0;
    cin >> T;
    for(int i = 0; i < T; i ++){
        int k, n, ans[14] = {0};
        cin >> k >> n;
        for (int j = 1; j <= n; j++){
            ans[j - 1] = j;
        }//기본 케이스를 만들어주는 과정
        for (int j = 0; j < k; j++){
            for (int ii = 1; ii < n; ii++){
                ans[ii] += ans[ii - 1];
            }
        }//아래부터 위로 쭉 올라가는 과정
        cout << ans[n - 1] << endl;
    }
}