2011번 - 암호코드
문제 풀이 시간 : 30분
문제 요약 :
- A를 1, B를 2와 같이 Z까지 암호화를 한다.
- 암호화된 문장을 보고 해석할 수 있는 경우의 수를 구한다.
문제 풀이 :
이 문제는 딱 보자마자 dp로 풀어야 겠구나 라는걸 알 수 있었다.
근데 dp는 항상 그렇듯 dp라는 것은 알 수 있지만
어떤 방식으로 풀어야할지 생각하는데 더 오래 걸리는 것 같다.
예제를 보면서 이것저것 적어보다가 하나의 규칙성을 찾게 되었다.
예제와 같은 25114라는 암호문이 주어졌다고 할 때,
우리는 맨 앞에 한 칸이 있다고 생각하고 경우의 수를 생각하면 된다.
위 경우에서는 2는 한가지 경우만 있기 때문에 1이라는 경우의 수를 가지게 된다.
여기서 다음 암호인 5가 온다면 두가지 경우의 수가 생긴다.
그래서 처음에는 2의 경우의 수인 1에다가 2를 곱해줘야하나?
하고 끝까지 해보니
8 이라는 경우의 수가 나온다.
그래서 다시 다른 방식을 생각해보다가
갑자기 피보나치가 나의 뇌리를 스쳐갔다.
그랬더니 마법처럼 답이 나왔다.
먼저 이렇게 코드를 짜보았다.
초기 핵심 코드
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int n = input.length();
input = '9' + input; //맨 앞에 임의의 수 넣어줌
int[] dp = new int[input.length() + 1];
dp[0] = 1; //첫번째 경우는 항상 1
for (int i = 1; i <= n; i++) {
if (input.charAt(i - 1) == '1') { //전의 수가 1이라면 현재 무슨 수가 와도 상관없음
dp[i] = dp[i - 1] + dp[i - 2];
} else if (input.charAt(i - 1) == '2') { //전의 수가 2라면 현재 6이하의 수가 와야함.
if (input.charAt(i) <= '6') {
dp[i] = dp[i - 1] + dp[i - 2];
}
} else { //두 경우 다 아니라면 전의 경우의 수 가져옴
dp[i] = dp[i - 1];
}
}하지만 이렇게 했더니 14%에서 틀렸다.
왜일까???
바로 현재 수가 0일 때,
다른 처리를 해주어야한다.
아래와 같은 경우가 있을 때,
0이 온다면 전에 1,2 만 올 수 있고,
1,2 가 있더라도 전의 경우의 수를 그대로 가져와야 한다.
for (int i = 1; i <= n; i++) {
if (input.charAt(i) == '0' && (input.charAt(i - 1) != '1' && input.charAt(i - 1) != '2')) {
dp[n] = 0; //현재 수가 0인데 앞에 1,2가 아니라면 될 수 없는 경우
break;
} else if (input.charAt(i) == '0' && (input.charAt(i - 1) == '1' || input.charAt(i - 1) == '2')) {
dp[i] = dp[i - 1]; //현재 수가 0이고 앞의 수가 1,2라면 경우의 수 그대로 가져옴
} else if (input.charAt(i - 1) == '1') {
dp[i] = (dp[i - 1] + dp[i - 2]);
} else if (input.charAt(i - 1) == '2') {
if (input.charAt(i) <= '6') {
dp[i] = (dp[i - 1] + dp[i - 2]);
} else {
dp[i] = dp[i - 1];
}
} else {
dp[i] = dp[i - 1];
}
}이렇게 해주었더니
결과는?
또 틀렸다
왜???
아래의 경우를 보자.
현재 코드에서는 0이 왔기 때문에 전의 경우인 3을 그대로 가져와 저장한다.
하지만, 0이 오면 앞의 1,2는 고정적으로 0과 함께해야한다.
그래서 결국 아래와 같다.
즉, 현재 수가 0이고, 전의 수가 1,2라면 위와 같이
전전의 경우의 수를 가져와 전과 현재에 저장해야한다는 것이다.
for (int i = 1; i <= n; i++) {
if (input.charAt(i) == '0' && (input.charAt(i - 1) != '1' && input.charAt(i - 1) != '2')) {
dp[n] = 0;
break;
} else if (input.charAt(i) == '0' && (input.charAt(i - 1) == '1' || input.charAt(i - 1) == '2')) {
dp[i] = dp[i - 2] % 1000000; //현재 수가 0이고 전이 1,2라면 경우의 수가 1개뿐임.
dp[i-1] = dp[i];
} else if (input.charAt(i - 1) == '1') {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
} else if (input.charAt(i - 1) == '2') {
if (input.charAt(i) <= '6') {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000;
} else {
dp[i] = dp[i - 1] % 1000000;
}
} else {
dp[i] = dp[i - 1] % 1000000;
}
}그렇다면 왜 dp[i] = dp[i-1] + dp[i-2] 라는 식이 성립할까?
예시를 보고 생각해보자.
색으로 나타낸 것과 같이
두가지 경우의 수로 나뉠 수 있는 부분인 2511을 만드는 과정을 본다면
25의 경우인 2,5 / 25 에 11 을 붙이는 경우,
251의 경우인 2,5,1 / 25,1 에 1 을 붙이는 경우로 나뉘게 된다.
따라서 dp[i] = dp[i-1]+dp[i-2] 라는 식이 성립하는 것이다.
함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.