문제 정보
플랫폼 : 백준
분류 : Dynamic Programming (동적 프로그래밍)
난이도 : 실버2
링크 : https://www.acmicpc.net/problem/15988
시간제한 및 메모리 제한 검증
O(n) 풀이 : 시간제한 ok
자료형 : 최대 30억 이므로 long
풀이
주말동안 Dynamic Programming 유형인 [1, 2, 3 더하기] 시리즈의 문제를 풀어봤다.
사실 어제부터 포스팅을 하려고 했는데, 머리자르느라 시간이 늦어서 쉬었다.
만약, 1, 2, 3 더하기 (1)을 풀지 않았거나, 풀이를 보지 않았다면 이곳을 클릭하여 풀이를 먼저 보고오자!
점화식
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; // (n >= 4)
1, 2, 3 더하기(1)과 같은 유형이다. 그러나 차이점이라고는, n이 100만인 점. 그리고 %1_000_000_009 로 나눈 값을 출력해야 한다는 점이다.
처음부터 끝까지 모두 더하고 % 연산을 하나,
더하는 중간중간 % 연산을 하고 출력하나 결과는 같다.
즉, (A+B+C...) % n == ((A%10) + (B%10) + (C%10) + ...) % n이다.
모듈러 연산의 분배법칙으로 인한 결과인데,
자세한 내용은 이곳을 클릭하여 증명방법을 참고하자!
이 문제에서 해당 증명을 적용하는 것은,
dp[n] = dp[n-1] + dp[n-2] + dp[n-3]; // (n >= 4)
으로 dp[n]을 구하고, 출력에서 dp[n] % 1_000_000_009가 아니라
dp[n] = (dp[n-1] + dp[n-2] + dp[n-3]) % 1_000_000_009;
를 통해 계산 중간중간에 %연산이 적용된 dp[n]을 저장하는 것이다.
만약 첫 번째 방법을 쓰면 오버플로우로 인해 정상적이지 않은 값이 들어오게 된다.
또한, dp[]가 int형으로 선언돼있고,
dp[n-1], dp[n-2], dp[n-3]이 각각 10억이라면
(dp[n-1] + dp[n-2] + dp[n-3])이 30억이 되므로 이 또한 오버플로우가 난다.
따라서 dp[]는 long형으로 선언하여 30억도 정상적으로 더하여 % 연산을 한다.
[점화식 설명]
4를 만들어보자.
1을 만드는 경우에 3을 더해주고,
2를 만드는 경우에 2를 더해주고,
3을 만드는 경우에 1을 더해주면 4가 된다.
이해를 위해 그림을 준비했다. 어렵지 않다.
참고로 1, 2, 3까지는 각각 자기 자신이 들어올 수 있으므로 1,2,3까지는 경우의수를 미리 dp에 입력하고, 4부터 dp를 돌린다.
코드
import java.io.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = stoi(br.readLine());
long dp[] = new long[1_000_001];
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for(int i = 4; i <= 1_000_000; i++)
dp[i] = (dp[i-1] + dp[i-2] + dp[i-3]) % 1_000_000_009;
for(int i = 0; i < n; i++){
System.out.println(dp[stoi(br.readLine())]);
}
}
public static int stoi(String str) {return Integer.parseInt(str);}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
