[백준] 17213번 : 과일 서리 – JAVA [자바]

 

 

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

17213번: 과일 서리

 

 

 

 

---

 

• 문제

 

---

 

• 풀이 방법

이 문제는 다이나믹 프로그래밍 (DP) 문제이니 DP 이론은 밑에 링크를 참고하면 되겠다.

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

 

 

 

이 문제는 2차원 DP 문제이다. 그리고 난이도는 solved.ac에서 실버 1로 되어 있다. 아마 DP 문제를 어느 정도 풀어봤고 2차원 배열 DP 문제를 조금 풀어봤으면 그래도 어렵지 않게 풀 수 있는 수준의 문제였다. 그리고 값 범위도 1 ≤ n ≤ 10 , 1 ≤ m ≤ 30여서 int형으로 구현해도 충분히 맞힐 수 있는 문제였다.

 

일단 n = 1이라고 가정해보자.

n = 1이면 m이 몇이 돼도 없다. 예를 들어서 사과 30개를 훔칠 수 있는 방법은 사과 30개밖에 없기 때문이다.

 

n = 2일 때를 한번 보자. 

예를 들어서 사과랑 포도가 있다고 하겠다. 

사과, 포도 해서 총 2개가 있으면 사과, 포도 각각 1개씩 훔칠 수 있다. 이거를 {1, 1}로 표현하겠다.

사과, 포도 3개가 있으면 {1, 2} 또는 {2, 1}로 표현할 수 있으므로 2가지의 방법이 있다.

사과, 포도 4개가 있으면 {1, 3}, {2, 2}, 또는 {3, 1}로 3가지의 방법이 있다.

그래서 n = 2 일 때 m-1개의 방법의 수가 있다.

 

만약 n = 3일 때는 어떻게 할까?

예를 들어서 사과, 포도, 배가 있다고 가정을 하겠다.

n = 3, m = 3 이면 각각 1개씩 할 수 있으므로 {1, 1, 1}, 즉 1개의 방법이 있다.

n = 3, m = 4 이면 {1, 1, 2}, {1, 2, 1} 또는 {2, 1, 1}로 수 있다.

그래서 n = 3 이면 

일단 첫 과일을 1개만 가져간다고 하면 나머지 과일 2개를 m-1개 가져가는 상황이 나온다. 따라서 표로 한번 나타내 보겠다.

 

행이 m이고 열이 n이다.

1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
0	1	2	3	4	5	6	7	8	9
0	0	1	3	6	15	21	28	36	44

 

---

 

• 풀이

 

import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int m = Integer.parseInt(br.readLine());
    int[][] dp = new int[11][31];
    for (int i = 1; i <= m; i++) {
      dp[1][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
      dp[i][i] = 1;
    }
    for (int i = 2; i <= n; i++) {
      for (int j = i; j <= m; j++) {
        dp[i][j] = dp[i][j-1] + dp[i-1][j-1];
      }
    }
    System.out.print(dp[n][m]);
  }
}

 

 

 

---

 

 

• 후기

그렇게 어렵지 않은 실버 1 DP 문제였던 거 같다.