[코딩테스트] 백준 #2775 문제 풀이

문제를 읽으면 되게 복잡해보인다.

처음에는 반복문을 이용해서 문제를 풀어야 하나 고민을 하고 끄적끄적 거리면서 생각을 해봤다. 예시에 있는 수들을 적어가면서 풀려고 했지만 딱히 어떻게 반복문을 써야할 지도 모르겠었다. 하지만 이렇게 어떤 순열의 구조를 가지고 있는 문제를 풀 때에는 규칙을 찾으려는 노력을 하면 생각보다 문제가 금방 풀린다.

규칙을 찾아서 간단하게 생각해보자

위에 문제도 (k,n)으로 두면 내가 그렸던 오른쪽 메모같이 전에 칸과 밑에 칸을 더하면 답이 나온다. 한마디로 (k,n) = (k,n-1) + (k-1,n)으로 하면 답이 구해진다. 여기에다 재귀함수를 사용한다면 끝이다.

n이 1이면 무조건 1을 출력하고 k가 0이면 n의 값을 출력하는 함수로 만들어주자.

최종 코드

#include <iostream>

using namespace std;

int getNumber(int a, int b)
{
    if(a == 0) return b;
    
    if(b == 1) return 1;
    
    return (getNumber(a-1, b) + getNumber(a, b-1));
}

int main()
{
    int testCase;
    int floor;
    int room;
    
    cin >> testCase;
    
    for(int i=0; i < testCase; i++)
    {
        cin >> floor;
        cin >> room;
        
        cout << getNumber(floor, room);
    }
}