[백준] 15990번 : 1, 2, 3 더하기 5 – JAVA [자바]

 

 

 

 

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

15990번: 1, 2, 3 더하기 5

 

 

 

 

 

 

---

 

• 문제

 

 

---

 

• 풀이 방법

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

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

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

 

 

 

이 문제는 전형적인 2차원 DP 문제이다. 그리고 난이도는 solved.ac에서 실버 2로 되어 있다. 실버 2 문제 치고는 정답 비율이 조금 낮은거 같다. 아마도 주어지는 n이 커질수록 1, 2, 3으로 나타낼 수 있는 방법이 너무 커져서 int의 범위를 초과하기 때문일거다. 그래서 배열을 int형 대신 long으로 만들어야지 범위를 초과 안 하고 맞는 답을 제출할 수 있다.

 

추가로 이 문제에서 어려운 점은 같은 수를 두번 이상 사용하면 안 되는 것이다. 이 문제는 RGB 거리와 매우 흡사하다. 2차원 배열을 만들어서 풀 면 된다. 

 

배열 dp[n][4]를 만들면 된다. 

dp[n][1]에는 이전 숫자에서 1을 더하고 연속으로 안 겹치게 하는 개수를 쓰면 되고 dp[n][2]에는 dp[n-2]에서 2를 더하고 2와 안 겹치게 하는 개수를 쓰면 된다. dp[n][3]도 똑같은 방식으로 하고 dp[n][4]에는 dp[n][1] + dp[n][2] + dp[n][3]을 더한 개수를 포함시켜 주면 된다.

 

그리고 가장 중요한 안 겹치게 하는 것은 바로 같은 수를 두 번 이상 연속해서 사용하면 안 된다는 것이다. 예를 들어 n=2를 보자. 

dp[1][1] = 1 (1)

dp[1][2] = dp[1][3] = 0이다. 1을 2나 3으로 표현할 수 없기 때문이다.

근데 n = 2 일때 1 + 1 으로도 2를 표현할 수 있지만 이는 같은 수를 반복한 거 여서 제외시켜야 된다.

따라서 2도 2로만 표현할 수 있기 때문에 dp[2][1] = dp[2][3] = 0이고 dp[2][2] = 1이다.

 

n = 3일 때 1 + 2를 해도 3이고 2 + 1을 해도 3이다. 그리고 3 = 3 이기도 하다.

따라서 dp[3][1] = dp[3][2] = dp[3][3] = 1이다.

이는 어떻게 된거냐면

dp[3][1] = dp[2][2] + dp[2][3] = 1

dp[3][2] = dp[1][1] + dp[1][3] = 1

dp[3][3] = 1

 

따라서 공식은 다음이 되겠다.

dp[n][1] = dp[n-1][2] + dp[n-1][3]

dp[n][2] = dp[n-2][1] + dp[n-2][3]

dp[n][3] = dp[n-3][1] + dp[n-3][2]

 

이 공식으로 수가 long의 범위 안에 있는 것만 확인해주면 된다.

예를 들면 

dp[n][1] = (dp[n-1][2] % 1000000009 + dp[n-1][3] % 1000000009) % 1000000009 를 해주면 된다.

 

밑에는 1 ≤ n ≤ 10 까지의 예시다.

 

n	1	2	3	sum
1	1	0	0	1
2	0	1	0	1
3	1	1	1	3
4	2	0	1	3
5	1	2	1	4
6	3	3	2	8
7	5	2	2	9
8	4	5	3	12
9	8	7	6	21
10	13	7	7	27

 

 

---

 

• 풀이

import java.io.*;
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());
    int max = 0;
    int[] ns = new int[t];
    for (int i = 0 ; i < t; i++) {
      int n = Integer.parseInt(br.readLine());
      ns[i] = n;
      max = Math.max(max, n);
    }
    long[][] dp = new long[100001][4];
    dp[1][0] = dp[1][3] = 1;
    dp[2][1] = dp[2][3] = 1;
    dp[3][0] = dp[3][1] = dp[3][2] = 1;
    dp[3][3] = 3;
    for (int i = 4; i <= max; i++) {
      dp[i][0] = ((dp[i-1][1]%1000000009) + (dp[i-1][2]%1000000009))%1000000009;
      dp[i][1] = ((dp[i-2][0]%1000000009) + (dp[i-2][2]%1000000009))%1000000009;
      dp[i][2] = ((dp[i-3][0]%1000000009) + (dp[i-3][1]%1000000009))%1000000009;
      dp[i][3] = (dp[i][0]+dp[i][1]+dp[i][2]) % 1000000009;
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < t; i++) {
      int num = ns[i];
      sb.append(dp[num][3] + "\n");
    }
    System.out.print(sb);
  }
}

 

 

 

---

 

• 후기

솔직히 실버 2 문제여서 그런지 그렇게 어렵지 않았고 전형적인 2차원 배열 DP 문제였다. 이 문제를 풀 수 있으면 나머지 2차원 배열 DP 문제들도 풀 수 있을거 같다.