[BOJ 10250] ACM 호텔

1) 문제 링크

https://www.acmicpc.net/problem/10250

2) 접근

아파트의 각 방을 좌표평면 위의 점에 대응시켜 생각했다. 처음에는 시그마를 몇 번씩 중첩시켜야 하나…하는 생각도 들었는데, 알고보니 문제를 잘못 이해하고 있었다. 문제를 다시 이해하고 접근한 결과 이항계수와 관련이 있음을 깨닫고 재귀함수로 combination 계산을 구현하여 답을 냈다.

3) 풀이

#include <iostream>
using namespace std;

int com(int n, int r){
    if(n == 1) { return 1; }
    if(r == 0 || r == n) { return 1; }
    return com(n-1, r-1) + com(n-1, r);
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t, k, n;
    cin >> t;

    for(int i=0; i<t; ++i){
        cin >> k >> n;
        cout << com(n+k, n-1) << '\n';
    }
    return 0;
}

4) 피드백

Combination 계산을 재귀함수를 쓰지 않고 O(1)에 계산하는 방법은 없을지 찾아보았다.

응 그딴 거 없어 ^^

그.러.나. Memoization을 써서 재귀를 돌리거나 아예 combination 배열을 처음에 세팅하고 가면 0ms를 띄울 수 있음을 깨달았다. (memoization 귀찮아서 안 했는데…) 앞으로 재귀 횟수가 많아질 것 같은 재귀함수를 다룰 때는 필수적으로 memoization을 해야겠다.