[BOJ] 15990 1,2,3 더하기 5 - JAVA

1. 문제

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

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1+2+1
1+3
3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

2. 풀이

dp 채우기

2차원 배열을 사용했다. [숫자][해당 숫자를 만들기 위해 마지막으로 더한 숫자]라고 보면 된다.

n=1일 때 1

n=2일 때 2

n=3일 때 1+2, 2+1, 3

이 세 가지 경우가 있으므로 처음에 저장해두고 다음 숫자를 채운다.

 

MOD 연산에서

(A + B)%MOD = (A%MOD + B%MOD)%MOD와 동일하다. (이렇게 해야 오버플로우가 나지 않는다)

dp에 저장된 값은 모두 연산이 적용된 값이므로 dp[num]에 이전 값 합에 MOD연산을 한 번 적용시킨 값을 저장하면 된다.

int MOD = 1_000_000_009;
int[][] dp = new int[100001][4];
dp[1][1] = dp[2][2] = dp[3][3] = 1;
dp[3][1] = 1;
dp[3][2] = 1;

for(int num=4;num<100001;num++){
   dp[num][1] = (dp[num-1][2] + dp[num-1][3])%MOD;
   dp[num][2] = (dp[num-2][1] + dp[num-2][3])%MOD;
   dp[num][3] = (dp[num-3][1] + dp[num-3][2])%MOD;
}

 

출력

테스트케이스 수만큼 반복하면서 StringBuilder에 정답을 저장한다.

이때, 오버플로우를 막기 위해서 두 수를 더하면 바로 MOD연산을 수행한다.

(dp[n][1]+dp[n][2])%MOD 한 값에 dp[n][3]을 더하고, 그 값을 다시 MOD연산한 것이 정답이다.

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(in.readLine());
StringBuilder sb = new StringBuilder();
int n;
for(int tc=0;tc<T;tc++){
   n = Integer.parseInt(in.readLine());
   sb.append(((dp[n][1] +dp[n][2])%MOD+dp[n][3])%MOD).append('\n');
}

System.out.print(sb);

 

전체 코드

import java.io.*;

public class BOJ_15990_123더하기5 {
   public static void main(String[] args) throws IOException {
      int MOD = 1_000_000_009;
      int[][] dp = new int[100001][4];
      dp[1][1] = dp[2][2] = dp[3][3] = 1;
      dp[3][1] = 1;
      dp[3][2] = 1;

      for(int num=4;num<100001;num++){
         dp[num][1] = (dp[num-1][2] + dp[num-1][3])%MOD;
         dp[num][2] = (dp[num-2][1] + dp[num-2][3])%MOD;
         dp[num][3] = (dp[num-3][1] + dp[num-3][2])%MOD;
      }

      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();
      int n;
      for(int tc=0;tc<T;tc++){
         n = Integer.parseInt(in.readLine());
         sb.append(((dp[n][1] +dp[n][2])%MOD+dp[n][3])%MOD).append('\n');
      }

      System.out.print(sb);
   }
}

---

3. 결과