[C언어] 백준 1010 : 다리 놓기

백준 1010 : 다리 놓기

 

문제 링크

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

1010번: 다리 놓기

 

 

문제 내용

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

 

 

 

Idea

얼핏 보면 단순 조합 문제로 수학적으로 계산할 수 있지만, 계산 도중 자료형이 처리할 수 있는 수의 범위를 넘어설 가능성이 매우 크므로 이러한 방법으로는 코딩할 수 없다.

 

따라서 다이나믹 프로그래밍(dynamic programming) 방법을 활용하여 문제를 해결하였다.

역시 dp는 점화식을 세우고 이해하면 쉬운 것 같다. (찾는게 힘들 뿐)

 

번외로 dp로 해결한 다음에 궁금해서 dfs 방식으로 조합을 만들고 카운트하는 방식으로 만들어봤는데 정답은 잘 나왔었지만 시간 초과가 걸렸다. 역시 dp가 빠르긴 한 듯... 

 

 

Code

#include <stdio.h>
#include <string.h>
 
int dp[31][31];
 
int main()
{
    int TC;
    int n, m;
    int size, result;
 
    scanf("%d", &TC);
    for (int test_case = 0; test_case < TC; test_case++)
    {
        scanf("%d %d", &n, &m);
        memset(dp, 0, sizeof(dp));
        size = m - n;
 
        // init
        for (int i = 1; i <= size + 1; i++)
            dp[1][i] = 1;
        // dp
        for (int i = 2; i <= n; i++)
            for (int j = i; j <= i + size; j++)
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
        // result
        result = 0;
        for (int i = n; i <= m; i++)
            result += dp[n][i];
        printf("%d\n", result);
    }
    return (0);
}