[백준] 1010 - 다리 놓기

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

문제 탐색하기

1) 문제 분석

서쪽 사이트 N개
동쪽 사이트 M개
서쪽 사이트 개수만큼 다리를 지어야 하며,
한 사이트에는 최대 한 개의 다리만 연결
다리는 서로 겹칠 수 없음→ 조합(Combination) 문제
서쪽 사이트 N개를 동쪽 사이트 M개에서 선택하여 연결해야 하므로
- 경우의 수 = M C N = M! / (N! * (M - N)!)
이를 점화식으로 표현하면
- dp[n][m] = dp[n][m - 1] + dp[n - 1][m - 1]
초기 조건
- dp[0][m] = 1 (0개 선택 = 경우의 수 1)
- dp[n][n] = 1 (같은 수 선택 = 경우의 수 1)

2) 가능한 시간복잡도

(1) 입력 처리 : O(T)

(2) DP 테이블 생성 : O(N * M)

(3) DP 테이블 채우기 : O(N * M)

(4) 테스트 케이스 처리 : O(T)

(5) 총 시간복잡도 : O(T * N * M)

-> 최대 N, M < 30 이므로 충분히 빠르게 동작한다.

3) 알고리즘 선택 이유

이 문제는 이전 계산 결과를 재사용하는 전형적인 DP 문제이며, 중복 하위 문제가 발생하므로 Dynamic Programming(동적 프로그래밍)으로 풀이가 적합하다고 생각했다.
조합 공식 자체를 점화식으로 구현할 수 있기에, DP 테이블을 이용하여 풀기로 결정했다.
재귀 + 메모이제이션(top-down)도 가능하지만, 반복문(bottom-up)이 더 직관적이라 선택했다.

잠깐! Dynamic Programming(DP, 동적 프로그래밍)에 대한 간단한 설명, 그리고 관련 예시 문제는 여기를 참고하자.

코드 설계하기

1. 실행 구조

1) 입력 처리

2) DP 테이블 초기화

3) 점화식 채우기

4) 테스트 케이스별 정답 출력

2. 고민이 되었던 부분

1) 조합을 구현하는 방법

단순히 팩토리얼로 조합을 구현하는 방법도 있지만, 팩토리얼 계산 중 오버플로우 가능성이나 계산 중복을 피하기 위해 점화식으로 접근했다.
그렇다보니, 점화식 세우기가 핵심이었고, 이를 통해 조합 문제도 DP로 해결 가능하다는 사실을 재확인할 수 있었다.
또한, 입력값이 매우 작기에 메모이제이션 재귀(top-down) 방식도 충분히 가능했지만, 실수 위험이 적은 반복문(bottom-up) 방식을 선택했다.

정답 코드

JavaScript

// 사용 언어 : Javascript


// 입력 처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const repeatCount = Number(input[0]);
input.shift();

// 테스트 케이스 처리
const testCases = input.map(line => {
    const [N, M] = line.trim().split(' ').map(Number);
    return { N, M };
});

// 조합 함수 (DP)
function combination(N, M) {
    const dp = Array.from({ length: N + 1 }, () => Array(M + 1).fill(0));

    for (let n = 0; n <= N; n++) {
        for (let m = 0; m <= M; m++) {
            if (n === 0 || n === m) {
                dp[n][m] = 1;
            } else if (n < m) {
                dp[n][m] = dp[n][m - 1] + dp[n - 1][m - 1];
            }
        }
    }

    return dp[N][M];
}

// 결과 출력
for (let i = 0; i < repeatCount; i++) {
    const { N, M } = testCases[i];
    console.log(combination(N, M));
}

마무리하며

알고리즘 문제를 풀 때 종종 공식에만 집착하게 되는 경우가 많았는데, 이번 문제를 풀면서 느낀 점은 수학 공식을 그대로 적용하는 것보다는 문제를 “점화식”으로 전개할 수 있는지를 먼저 고민하고, 그 안에서 반복되는 패턴이나 규칙을 찾아내는 사고의 과정이 더 중요하다는 것이었다. 단순한 공식을 암기하는 것만으로는 응용문제에서 쉽게 무너질 수 있음을 다시 확인한 셈이다.

무엇보다 중요한 건 문제를 만나면 “어떻게 푸는지”가 아니라 “왜 이렇게 푸는지”를 먼저 고민하는 습관이라는 점이다. 앞으로도 문제를 접할 때 최적화된 풀이법이 무엇인지, 혹은 더 효율적인 알고리즘이 존재하는지를 차분하게 분석하고, 다양한 접근법을 고려하면서 구현하는 자세를 유지하고 싶다. 이번 문제처럼 비교적 단순한 문제도 깊이 생각해보면 많은 배움을 얻을 수 있다는 점을 다시금 느낀 의미 있는 문제였다.

최근 글