1. 문제
15990번: 1, 2, 3 더하기 5
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
www.acmicpc.net
정수 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. 결과
'코딩테스트 > BOJ' 카테고리의 다른 글
[BOJ] 15663 N과 M (9) - JAVA (0) | 2023.07.12 |
---|---|
[BOJ] 1343 폴리오미노 - JAVA (0) | 2023.07.10 |
[BOJ] 16194 카드 구매하기 2 - JAVA (0) | 2023.07.08 |
[BOJ] 10826 피보나치 수 4 - JAVA (0) | 2023.07.07 |
[BOJ] 1043 거짓말 - JAVA (0) | 2023.07.04 |
댓글