백준 1010번 다리 놓기 (C++)

문제 링크 : www.acmicpc.net/problem/1010

1010번: 다리 놓기

이 문제는 난이도가 실버 5단계이다.

때문에 난이도만 보아서는 얼핏보면 굉장히 쉬운 문제이지만, 시간 제한이 0.5초라는 점을 간과한다면 쉽게 틀릴 수 있는 문제다.

 

문제를 읽으면 '조합'문제라는 생각이 곧 바로 떠오를 것이다.

포인트는 그 조합을 어떻게 구현하느냐인데, 나는 처음에 파스칼의 삼각형 이론과 동적 프로그래밍(DP) 조합을 통해 문제에 접근했다. 그러나 계속 시간초과를 겪었다.

파스칼의 삼각형 이론 : n C r = n-1 C r-1 + n-1 C r

<파스칼의 삼각형과 DP를 조합한 틀린 코드>

#include <iostream>
#define MAX 30
using namespace std;

int arr[MAX][MAX] = {0,};

int Bridge(int m, int n){
    if(n==m||n==0) return 1;
    else if(arr[n][m]) return arr[n][m];
    arr[m][n] = Bridge(m-1,n-1)+Bridge(m-1,n);
    return arr[m][n];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, m = 0, t = 0;
    cin >> t;
    while(t--){
        cin >> n >> m;
        cout << Bridge(m,n) << "\n";
    }
    return 0;
}

고민을 몇 번 해봤는데, 문제의 난이도가 실버 5라는 점을 생각하면 풀이 자체가 굉장히 쉬울것이라는 생각이 들었다.

그러다 무식하게 조합을 계산하는 방법을 구현했고, 결국 이게 문제에서 원하는 정답이었다.

 

한 가지 포인트는, 만에 하나 시간초과를 방지하기 위해 9C7과 같이 n이 m-n보다 큰 경우, n을 m-n으로 치환했다는 점이다.

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, m = 0, t = 0, temp = 0;
    cin >> t;
    while(t--){
        long long ans = 1;
        cin >> n >> m;
        temp = m;
        m = n; 
        n = temp; // n:1, m:5 -> n:5, m:1 
        if(m>n-m) m = n-m; // 시간 초과 방지
        for(int i=n; i>n-m; i--) ans *= i;
        for(int j=m; j>=1; j--) ans /= j;
        cout << ans << "\n";
    }
    return 0;
}

 

무수한 뻘짓의 흔적들