암호코드 (https://www.acmicpc.net/problem/2011)
기본점화식은 아래와 같다.
dp[i] = dp[i - 1] + dp[i - 2];
무슨 의미인지 한참을 생각했다.
ex) 알파벳은 1~26 사이의 숫자로 구성되며 나머지 숫자는 성립되지 않으므로 모두 예외적인 상황이다.
경우의 수 계산을 쉽게하기 위해 25114가 아닌 25134를 사용한다.
25134
답 : 6
0 1
1 1 (2) : 2밖에 없으니 표현할 수 있는 경우는 1.
2 2 (25) : 알파벳이 성립함. 2,5 / 25 여기서 dp[0]=1로 초기화 하지않으면 해당 값에 대한 계산이 불가.
3 2 (51) : 26을 초과하므로 2,5 / 25 뒤에 1을 붙이는 경우만 존재. 단순하게 붙이는 경우엔
경우의 수 변경 없음.
4 4 (13) : 기본 점화식으로 계산
5 6 (14) : 기본 점화식 기본 점화식 계산
dp 초기화를 1로 해야하는 이유는 위의 점화식의 d[i-2] 계산 때문이다.
dp[0] = 1;
dp[1] = 1;
피보나치 수열에 조건이 많은 경우처럼 보인다.
이해를 위해 2513 까지만 따져보면
1단계 :
2 -> 2를 배치하는 경우 1가지
2단계 :
2,5 / 25 -> 2 2가지
3단계 (알파벳 성립 안하면 경우의 수 변화는 없다.)
2,5,1 / 251 -> 2가지
4단계
2, 5,1,1 / 25, 1 ,1 (1을 연달아 붙인 경우 d[i-1]와 같다)
2,5,11 / 25, 11 (1두개를 합한 경우 d[i-2]와 같다.)
여기 까지만 보면 1, 11 => 2가지 경우를 d[i-1]*2 로 구했는지 dp[i - 1] + dp[i - 2] 로 구했는지 알 수가 없다.
사실 이부분 이해하는데 시간이 엄청 걸린거 같다.
제대로 따져보기 위해 5단계를 거치면.
5단계
2,5,1,1,3 / 2,5,11,3 / 25, 1 ,1,3/ 25, 11, 3 (1을 연달아 붙인 경우 d[i-1]와 같다)
자 그렇다면 두개를 조합한 경우는 왜 d[i-2]가 되는가?
조합한 경우를 만드려면 이전 단계에 11로 된 수에서 1을 찢어와야한다.
위의 경우에서 맨 뒷자리를 모두 13으로 만들도록 구성을해보면 아래와 같다.
2, 5, 1, 13 / 2, 5 1, 13 (앞의 11에서 1을 뺏어옴) / 25, 1, 13 / 25,1,13(이하동문) => 중복을 제외한 2가지 경우
자, 만들고나니 중복되는 경우의 수가 보인다.
현재 만든 경우의 수에서 중복 2개를 제거하고, 조합된 수의 고정된 1,13을 지우고나면?
2, 1 / 25, 1 만 남게된다. 여기서 2단계의 경우의 수가 보이면 된 것이다.
따라서 4단계 경우의 수 = 3단계 경우의 수 + 2단계 경우의 수 라는 것이 이해가 돼야한다.
( d[i-1]*2 가 성립하지 않는 반례가되며, 단순히 d[i-1] + d[i-2] 가 된다는 점화식을 파악하는 것을 넘어 각 요소가 무엇을 의미하는지 알게 됨)
예외처리가 계속 틀려 멘붕이었는데 아래 글에서의 예제를 활용해 검증하니 AC되었다.
반례로 사용한 입력은 아래 글에서 참조.
출처 : https://www.acmicpc.net/board/view/44917
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static long[] dp;
static long MOD = 1000000L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String s = st.nextToken();
dp = new long[5001];
int N = s.length();
if( s.charAt(0)=='0') {
System.out.println("0");
return;
}
dp[0] = 1;
dp[1] = 1;
//first : i-2 , current : i-1
for (int i = 2; i <= s.length(); ++i) {
if (s.charAt(i-1)=='0') {
if( s.charAt(i-2) == '1' || s.charAt(i-2) == '2' ) { // 10 or 20
dp[i] = dp[i - 2] % MOD;
} else { // 30,40,50~ 모두 성립하지 않음.
dp[i] = 0;
}
} else { //0으로 시작하지 않는 경우.
int val = Integer.parseInt(s.subSequence(i - 2, i).toString());
//System.out.println("val : "+ val);
if (val >= 1 && val <= 9) {//0으로 시작한다는것? 앞자리가 20 or 30이라는 의미. 1203
dp[i] = dp[i - 1] % MOD;
}
else if (val >= 11 && val <= 26) {
dp[i] = dp[i - 1] + dp[i - 2] % MOD;
}else {
dp[i] = dp[i - 1] % MOD;
}
}
}
System.out.println(dp[N] % MOD);
/*
for (int i = 0; i <= N; ++i)
System.out.printf("%d %d\n", i, dp[i]);
System.out.println();
*/
}
}
