[백준] 1010번_다리 놓기_Java

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

👀 문제 접근

---

다리 놓기

서쪽 사이트 수만큼 동쪽 사이트에 다리를 지어야한다.

다리끼리는 서로 겹칠 수 없으며, 서쪽의 사이트 개수만큼 다리를 지어야한다.

🔎 해결 방식

---

입력

• 테스트 케이스 t 를 입력한다.
• for 문 순회를 하며 n 과 m 을 입력한다

경우의 수 구하기

• dp를 통해 경우의 수를 구한다.
• 결과를 저장할 배열 arr 를 선언한다.
  • 사이트가 0개 ~ n, m 개까지인 경우를 저장해야 하므로 배열 크기는 n + 1 및 m + 1 로 선언한다.
  • 서쪽 사이트가 0개일 때
    • 이 경우에 다리를 건설할 수 없다. 아무것도 하지 않는 경우 1가지이므로 1을 리턴한다.
  • 서쪽 사이트가 1개일 때
    • 이 경우에 다리는 m 개 건설할 수 있기 때문에 m 을 리턴한다.
  • 그외의 경우

    • 테이블을 그려보면 다음과 같다.

      n\m	0	1	2	3	4	5
      0	1	1	1	1	1	1
      1	0	1	2	3	4	5
      2	0	0	1	3	6	10

    • n 이 m 보다 클 경우 다리를 건설할 수 없다

      ❓n 이 0일 때 다리를 건설하지 않는 경우를 카운트 하는데 이건 왜 카운트 할 수 없을까?

      문제에서 서쪽 사이트 개수만큼 다리를 지어야한다는 조건이 있다.

      따라서 n 이 0일 경우에는 다리를 짓지 않는 조건을 포함할 수 있다.

      하지만 n 이 0보다 크고, m 이 0일 때 서쪽 사이트를 사용하더라도 동쪽 사이트로 이어질 수 없기 때문에 이 경우에는 카운트 하지 않는다.

    • n 이 2인 경우를 볼 때 dp[2][2] 는 dp[1][1] 과 dp[2][1] 을 더한 값과 같다. 또한 dp[2][3] 은 dp[1][2] 와 dp[2][2] 를 더한 값과 같다. 따라서 다음과 같은 식을 도출할 수 있다.

      $dp[i][j] = dp[i][j-1] + dp[i - 1][j - 1]$

💻 구현 코드

---

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

public class Main {
    public static long dp(int n, int m) {
        long[][] arr = new long[n + 1][m + 1];

        if (n == 0) return 1;
        else if (n == 1) return m;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0) {
                    arr[i][j] = 1;
                } else if (i != 0 && i > j) {
                    arr[i][j] = 0;
                } else {
                    arr[i][j] = arr[i - 1][j - 1] + arr[i][j - 1];
                }
            }
        }
        return arr[n][m];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            long answer = dp(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
            System.out.println(answer);
        }
    }
}

✨ 마무리

---

DP 문제를 풀어 보려고 해도 도무지 풀이 방법이 생각나지 않아 뒷걸음질 치게 되고, 결국엔 공부하는 걸 피하게 돼 버린다. DP 공포증?을 극복하고자 문제풀이 방식을 보더라도 계속 접해보려고 노력한다. 아직 홀로 풀 수 있는 문제는 피보나치 수열밖에 없지만.. 언젠가 골드 레벨 문제를 뿌시기 위해 낮은 레벨부터 차근차근 풀어보려 한다.