[Java] baekjoon_9095 : 1, 2, 3 더하기

다이나믹 프로그래밍

1, 2, 3 더하기 : Silver3

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

9095번: 1, 2, 3 더하기

 

 

풀이

import java.io.*;

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

    for (int i = 0; i < T; i++) {
      int sum = Integer.parseInt(br.readLine());

      int[] dp = new int[11];

      dp[1] = 1;
      dp[2] = 2;
      dp[3] = 4;

      for (int j = 4; j <= sum; j++) {
        dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
      }

      bw.write(dp[sum] + "\n");
    }
		
    br.close();
    bw.close();
  }
}

 

ㄴ 다이나믹 프로그래밍을 이용하도록 했다.

ㄴ dp 라는 배열을 생성하고, dp[sum] 는 정수 sum을 1, 2, 3 을 이용해 만든 조합으로 이루어져야한다.

 

예를 들면,
dp[1] 은 1로만 이루어질 수 있으므로 경우의 수가 1가지 이다.
sum = 1일 때,
1 
=> 1가지 이므로 dp[1] = 1

sum = 2일 때,
1 + 1
2
=> 2가지 이므로 d[2] = 2

sum = 3일 때,
1 + 1 + 1
1 + 2
2 + 1
3
=> 4가지 이므로 d[3] = 4

sum = 4일 때,
1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2
1 + 3
3 + 1
=> 7가지 이므로 d[4] = 7

 

ㄴ 그런데 sum = 4인 경우의 수에서 

 

1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2
3 + 1

1 + 3

=> 보라색 부분의 연산은 dp[3]에 포함된 경우의 수와 같다.

 

1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2

3 + 1
1 + 3


=> 초록색 부분의 연산은 dp[2]에 포함된 경우의 수와 같다.

 

1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2
3 + 1

1 + 3

=> 빨간색 부분의 연산은 dp[1]에 포함된 경우의 수이다.

 

 

sum 이 5인 경우,

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1

1 + 2 + 1 + 1

1 + 1 + 2 + 1

1 + 1 + 1 + 2

2 + 2 + 1

2 + 1 + 2

1  + 2 + 2

3 + 1 + 1

1 + 3 + 1

1 + 1 + 3

2 + 3

3 + 2

즉, dp[4] 는 결국 dp[3] + dp[2] + dp[1]을 더한 것과 같고,

dp[5] 는 dp[4] + dp[3] + dp[2]를 더한 것과 같다.

여기서 얻을 수 있는 점화식은 dp[sum] = dp[sum - 1] + dp[sum - 2] + dp[sum - 1] 이 된다.