[붙끝코] dp를 뿌서,,,(3) 11일차 (백준 1011)

오늘의 문제는 다리 놓기
입니다!!! 소리질러!!!!

📌 문제 탐색하기

1. 한 사이트에는 한 개의 다리만 놓일 수 있다.

2. 서로 다른 다리가 겹치면 안된다.

   M개중에 N개 선택 중복 허용 하지 않음-> 조합

• 입력:서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)
• 출력:다리를 지을 수 있는 경우의 수

📌 코드 설계하기

사실 저는 이 문제를 보자마자 아 이거 조합 문제네! 라고 떠올랐습니다.
고딩때 확통에서 개념문제로 나왔던 문제 아니냐구요!!ㅎㅎ
(이게 고딩 수학의 중요성인가봐요)

다리를 지을 수 있는 경우의 수는 mCn 이 되겠습니다~

사실 저는 처음 문제를 풀 때는 dp를 이용하지는 않았습니다.

첫번째 설계 과정 (시도 회차 수정 사항 참고)
1. 입력
• BufferedReader를 사용하여 입력
2. 반복문을 통한 각 테스트 케이스 처리:
• T 만큼 반복하며 각 테스트 케이스에 대해 N 과 M 을 입력
• StringTokenizer를 사용하여 입력된 값을 공백을 기준으로 분리
• N 과 M 을 정수로 변환하여 --> combi
3. 조합 계산 함수 combi:
• BigInteger
• combi(M, N)은 다음 공식을 사용하여 계산합니다:

이해를 돕기 위하여 제가 설계 과정에 썼던 풀이를 첨부 합니다:)

위 공식에 따라 for 루프를 돌며 result에 값을 처리
4. 결과 출력:
• BufferedWriter를 사용하여 결과를 출력.

사실 저는 이 코드에서 combi의 시간복잡도는 O(N)이고 전체프로그램의 시간 복잡도는 O(TXN)이기 때문에 그렇게 아주 최악이라고는 생각하지 않습니다.(?)

그래도 dp 유형을 풀고 있으니 역으로 어떻게 dp를 사용할 수 있을까를 고민해보았는데!!

혹시 다들 파스칼의 삼각형 떠오르시나요...?

다음 특징을 이용해서 점화식과 base case를 세우면 끝입니다!!

입력 출력 부분은 똑같고 combi 메소드만 보면
1. 이차원 배열 생성후 dp 초기화 (base-case)

int[][] dp = new int[31][31]; // DP 테이블 생성

for (int i = 0; i <= M; i++) {
    dp[i][0] = 1; // nC0 = 1
    dp[i][i] = 1; // nCn = 1
}

2. 점화식을 이용해 dp 채우기

for (int i = 1; i <= M; i++) {
    for (int j = 1; j <= N && j < i; j++) {
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    }
}

bottom-up 방식으로 dp 문제 구현 완성입니다!
확실히 dp유형의 문제는 dp 유형인지 알아 차리는게 어렵네요ㅠㅁㅠ

📌 시도 회차 수정 사항

1) 사실 저는 처음에는 dp를 사용하지 않았습니다...!
처음에 long형으로 했다가 overflow 문제로 틀렸습니다 결과가 나와서 BigInteger로 바꿨더니 통과하였습니다!

📌 정답 코드

1. 직접 구현

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine()); // 테스트 개수

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            bw.write(combi(M, N).toString() + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    // 조합을 계산하는 함수 (BigInteger 사용)
    static BigInteger combi(int M, int N) {
        BigInteger result = BigInteger.ONE; // 0&&1 팩토리얼== 1

        // mCn 계산
        for (int i = 0; i < N; i++) {
            result = result.multiply(BigInteger.valueOf(M - i));
            result = result.divide(BigInteger.valueOf(i + 1));
        }

        return result;
    }
}

2. dp 이용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 
        StringBuilder sb = new StringBuilder();

       
        for (int i = 0; i < T; i++) {
            String[] input = br.readLine().split(" ");
            int N = Integer.parseInt(input[0]); 
            int M = Integer.parseInt(input[1]); 
            sb.append(combi(M, N)).append('\n'); 
        }

        System.out.println(sb);
    }

    // 조합
    static int combi(int M, int N) {
        if (N == 0 || M == N) {
            return 1; 
        }

        int[][] dp = new int[31][31];

        // 초기화
        for (int i = 0; i <= M; i++) {
            dp[i][0] = 1; // nC0 = 1
            dp[i][i] = 1; // nCn = 1
        }

        // 채우기
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N && j < i; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }

        return dp[M][N];
    }
}

비교래보니깐 첫번째 코드의 시간 복잡도는 O(TXN) 이고 두번째 코드의 시간복잡도는 O(TXNXM) 입니다! 보니깐 dp가 중복 계산을 줄였지만 첫번째 코드가 더 시간 복잡도가 상대적으로 낮네요??

근데 백준에서는 첫번째 결과가 살짝 더 느린걸 봐서는 큰수 계산에서 BigInteger 연산이 느릴 수 있다는 점 때문인 것 같습니다. 1번

2번