[백준 / Java] 1010번: 다리 놓기 (실버5)

문제 풀이 날짜: 2023.08.29
포스트 작성일: 2023.08.30

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

동적 계획법, 조합론

 

키워드

백준 온라인 저지 1010번: 다리 놓기 (실버5)

 

풀이 접근법

• 큰 문제의 해가 작은 문제의 해를 포함하는 형태이므로 점화식을 세워볼 수 있다.
• i번째 사이트가 j번째 사이트를 선택하여 다리를 놓았다면, 그 이전에 i - 1번째 사이트가 세워놓았던 다리가 결정되어 있을 것이다. 이를 DP로 더하여 누적한다.
• 0번 출발지가 0번 도착지를 선택한다면 다리를 1개 세울 수 있다.
  • 0번 출발지가 1번 도착지를 선택해도 다리를 1개 세울 수 있다.
  • …
  • 1번 출발지가 3번 도착지를 선택한다면 그 이전에 0번 출발지는 0, 1, 2번 도착지를 선택한 경우의 수를 가지고 있다.
  • 3번 출발지가 4번 도착지를 선택한다면 그 이전에 2번 출발지가 0, 1, 2, 3 도착지를 선택한 경우의 수를 가지고 있으며, 그 이전의 경우의 수도 모두 포함한다.
  • 따라서 점화식은 DP[n][m] = ∑ DP[n-1][k] (k = 0 ~ j-1)​

 

코드

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

public class Main {

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

		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int tc = 0; tc < T; tc++) {

			String[] temp = br.readLine().split(" ");

			int N = Integer.parseInt(temp[0]);
			int M = Integer.parseInt(temp[1]);

			int[][] DP = new int[N][M];

			for (int i = 0; i < M; i++) {
				DP[0][i] = 1;
			}
			
			for (int i = 1; i < N; i++) {
				for(int j = 0; j < M; j++) {
					if(i > j) { continue; }
					
					for (int k = 0; k < j; k++) {
						DP[i][j] += DP[i - 1][k]; 
					}
				}
			}
			
			int result = 0;
			for(int i = 0; i < M; i++) {
				result += DP[N - 1][i];
			}
			
			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}
}

---

 

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/41aaeed58066dc701c40e93b194b966da2b74fbc/%EB%B0%B1%EC%A4%80/Silver/1010.%E2%80%85%EB%8B%A4%EB%A6%AC%E2%80%85%EB%86%93%EA%B8%B0/%EB%8B%A4%EB%A6%AC%E2%80%85%EB%86%93%EA%B8%B0.java