문제 정보
플랫폼 : 백준
분류 : Dynamic Programming (동적 프로그래밍)
난이도 : 실버3
링크 : https://www.acmicpc.net/problem/15990
시간제한 및 메모리 제한 검증
O(n) 풀이 : 시간제한 ok
자료형 : 최대 30억, long
풀이
주말동안 Dynamic Programming 유형인 [1, 2, 3 더하기] 시리즈의 문제를 풀어봤다.
사실 어제부터 포스팅을 하려고 했는데, 머리자르느라 시간이 늦어서 쉬었다.
만약, 이전 1, 2, 3 더하기 시리즈를 풀지 않았거나, 풀이를 보지 않았다면 이곳을 클릭하여 이전 풀이를 먼저 보고오자!
점화식
dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1_000_000_009;
dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1_000_000_009;
dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1_000_000_009; (n >= 4)
이 문제는 1,2,3 더하기 (4)와 같이, 2차원 배열을 사용한다. 이전 문제의 해설을 보지 않은 사람은 이곳을 클릭하여 풀이를 보고오면, 이해가 쉽다.
문제가 생각할게 많아졌다. 일단, 기존 1차원 배열이었던 점화식이 2차원배열로 바뀌었다.
dp[i][j] 에서 i: 임의의 정수, j: 수식이 j로 끝남
을 의미한다. 예시를 들어보면,
위 사진과 같다.
[점화식 설명]
*미리 말하지만, 그림 설명이 아래에 있다.
7을 1, 2, 3의 합으로 나타내보자.
4을 만드는 경우에 3을 더해주고,
5를 만드는 경우에 2를 더해주고,
6을 만드는 경우에 1을 더해주면 7이 된다.
그러나, 같은 수를 두 번 이상 연속해서 사용할 수 없다.
(이전에 사용한 값이 또 오면 안된다.)
1) 7를 만들 수 있는 수식 중에서,
1로 끝나는 수식 (마지막에 1을 더해주는 경우)은
6을 만드는 수식에서 2로 끝나는 것에 1을 더하는 것,
6을 만드는 수식에서 3으로 끝나는 것에 1을 더하는 것이다.
즉, dp[7][1] = dp[6][2] + dp[6][3]이다.
일반화하면, dp[n][1] = dp[n-1][2] + dp[n-1][3] 이다.
2) 7를 만들 수 있는 수식 중에서,
2로 끝나는 수식 (마지막에 2를 더해주는 경우)은
5를 만드는 수식에서 1로 끝나는 것에 2를 더하는 것,
5를 만드는 수식에서 3으로 끝나는 것에 2를 더하는 것이다.
즉, dp[7][2] = dp[5][1] + dp[5][3]이다.
일반화하면, dp[n][2] = dp[n-2][1] + dp[n-2][3] 이다.
3) 7를 만들 수 있는 수식 중에서,
3으로 끝나는 수식 (마지막에 3을 더해주는 경우)은
4를 만드는 수식에서 1로 끝나는 것에 3을 더하는 것,
4를 만드는 수식에서 2로 끝나는 것에 3을 더하는 것이다.
즉, dp[7][3] = dp[4][1] + dp[4][2]이다.
일반화하면, dp[n][3] = dp[n-3][1] + dp[n-3][2] 이다.
말로만 설명하면 어려우니, 7을 만드는 과정을 그림으로 설명하겠다.
위와 같은 과정을 통해
dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1_000_000_009;
dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1_000_000_009;
dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1_000_000_009; (n >= 4)라는 점화식이 나온다.
모듈러가 나오는 이유는, 10억9로 나누어 출력하라는 제한사항이 있기 때문이다. 마지막에 모듈러를 넣는 것이 아니라, 계산 과정 중간에 모듈러를 넣는 이유는 이곳을 참조하자.
코드
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = stoi(br.readLine());
long[][] dp = new long[100_001][4];
dp[1][1] = 1; // 1
dp[2][2] = 1; // 2
dp[3][1] = 1; // 2+1
dp[3][2] = 1; // 1+2
dp[3][3] = 1; // 3
for(int i = 4; i <= 100_000; i++) {
dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % 1_000_000_009;
dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % 1_000_000_009;
dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % 1_000_000_009;
}
for(int i = 0; i < n; i++) {
int t = stoi(br.readLine());
sb.append((dp[t][1] + dp[t][2] + dp[t][3]) % 1_000_000_009 + "\n");
}
System.out.println(sb);
}
public static int stoi(String str) {return Integer.parseInt(str);}
}더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
