난이도
실버 2
문제
https://www.acmicpc.net/problem/15988
풀이
문제 풀이
1. 가짜 문제 정의
i를 1,2,3의 합으로 나타내는 방법수
- 초기값 구하기
d[1] = 1 => 1개
d[2] = 2 / 1,1 => 2개
d[3] = 1,1,1 / 1,2 / 2,1 / 3 => 4개
- 점화식 구하기
d[4] = (d[3]+1) + (d[2]+2) + (d[1]+3)
=> d[4]는 d[3]에 각각 1씩 더해준 것,d[2]에 각각 2씩 더해준 것, d[1]에 각각 3씩 더해준것의 합과 같다.
따라서, 점화식은
d[i] = d[i-1]+d[i-2]+d[i-3]
어려웠던 점
여기서 어려웠던 점은 dp배열의 타입이 int이면 틀리고 long이면 맞았다.
단순하게 n이 백만이니까 int 아니야? 라고 생각했는데 dp 점화식 채울 때 덧셈을 하다보면 금방 int 범위를 초과한다는 사실을 간과했다.
아래와 같이 이해하며 어려움을 해결했다.
1) 피보나치로 이해하면 쉽다.
피보나치수를 직접 구해봤을 때 n=47일 때부터 int 범위를 초과한다. 따라서 이문제에서 백만이면 int 범위는 족히 넘는 것을 알 수 있다.
2) 나머지 연산을 취하는 것에서 힌트 얻기
나머지 연산을 1,000,000,009 이만큼 취하게 되면
나머지 연산하기 전에 값은 1,000,000,009*1,000,000,009이 나올 수 있다.
그렇다면 int 범위는 너무나 초과하므로 long 타입을 써야한다.
코드
package DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ15988 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
long[] dy = new long[1_000_001];
// 초기값
dy[1] = 1;
dy[2] = 2;
dy[3] = 4;
for (int i = 4; i <= 1_000_000; i++) {
dy[i] = (dy[i - 1] + dy[i - 2] + dy[i - 3]) %1_000_000_009;
}
while (t-- > 0) {
int n = Integer.parseInt(br.readLine());
System.out.println(dy[n]);
}
}
}
참고
Back-End Developer