[1010]다리 놓기

이 문제는 조합(combination)에 관한 문제이다. 이 문제를 풀려고 했을땐 동적 프로그래밍 문제인 줄 알았으나 많은 사람들이 조합으로 해결하였고 나 또한 조합 문제라고 생각했다. 동적프로그래밍으로 풀수도 있는진 모르겠다.

처음엔 간단하게 풀 수 있을거라 생각했지만 실제론 어려웠다.

어려웠던 점을 꼽자면 

 

1.변수가 담을 수 있는 숫자의 크기 제한

2.팩토리얼 연산의 한계

3.조합 함수 내에서의 예외 처리

 

1번의 경우 long long으로 팩토리얼 계산 결과 값을 담는 변수의 크기를 늘렸다. 2번의 경우 팩토리얼 연산의 크기를 줄이는 우회 방법을 사용하였다. 우연히도 오늘 책(종만북)에서 이 부분에 대한 해결법을 봤었고 이 문제에 대해 고민할때 책에 나온 부분을 다시 짚어보았다.

3번의 경우 크게 두 가지 경우에서 시간이 많이 걸렸다. 처음의 경우는 메모리 초과가 발생한 경우인데, 정확한 오류 문구는 기억 안나지만 아마 함수 호출이 길어지는 문제였을거다. 딱히 재귀함수를 사용하지... 않는다고 생각했는데 어느 부분이 마음에 걸렸다. 바로 초반부의 'if(x < y/2)'이 조건문이다. 처음엔 x <= y / 2 라고 작성하였는데 이럴 경우 예를 들면 y가 28이고 x가 14일 경우 무한 재귀 호출 문제에 빠진다. 이 부분을 <=에서 <으로 고치니 문제가 해결되었다. 두번째 경우는 N이 29이고 M이 29일 경우이다. 원래는 1이 나와야 하지만 내가 작성한 함수에선 2가 나왔다. 이 부분은 우회 접근 방법에서 28C29를 구하는 경우가 생겨서이다. 이 문제를 해결하기 위해 x가 y보다 크면 0을 반환하도록 하였다.

 

그렇게 해서 장정 3시간에 걸쳐 문제를 해결하였다. 앞으로도 발전없이 쭉 이럴거라고 생각하면 하기 싫어진다. 하면 할수록 발전할거라고 믿고 매일 한 문제는 꼭꼭 풀도록 하자!

 

아래는 해결 방법을 적은 코드.

#include <iostream>

using namespace std;

long long comb(const int& x, const int& y){
  if(x > y)
    return 0;
    
  if(x < y / 2){
    return comb(y-x, y);
  }
  else{
  long long n = 1;
  for(int i = x + 1; i <= y; i++)
    n *= i;
  long long m = 1;
  for(int i = y-x;i > 1; i--)
    m = m * i;
  return n / m;
  }
}

int main() {
  int count = 0;
int N = 0, M = 0;


cin >> count;

long long* results = new long long[count];

for(int i = 0; i < count; i++)
{
    cin >> N >> M;
    
    long long result = 0;
    
    if (M > 20)
      result = comb(N - 1, M - 1) + comb(N, M - 1);
    else
      result = comb(N, M);
    results[i] = result;
        
}

for(int i = 0; i < count; i++){
  cout << results[i] << endl;
}
}