Baekjoon 2011 암호코드
문제 이해
A를 1로, Z를 26으로 하는 암호문이 띄어쓰기 없이 최대 5000자리까지 주어진다.
영문자와 영문자 사이를 구분하는 기호가 없으니 하나씩 대입을 하면서 말이 되는 단어인지 확인해야 풀 수 있는 암호문이다.
예를 들어 25114가 주어진다고 하면 아래와 같은 경우의 수의 해석이 가능하다.
| 2 | 5 | 1 | 1 | 4 |
|---|---|---|---|---|
| B | E | A | A | D |
| 25 | 1 | 1 | 4 |
|---|---|---|---|
| Y | A | A | D |
| 25 | 1 | 14 |
|---|---|---|
| Y | A | N |
| 25 | 11 | 4 |
|---|---|---|
| Y | K | D |
| 2 | 5 | 11 | 4 |
|---|---|---|---|
| B | E | K | D |
| 2 | 5 | 1 | 14 |
|---|---|---|---|
| B | E | A | N |
따라서 25114의 경우의 수는 6개 이다.
이와 같이 주어진 암호문을 조합하여 만들 수 있는 경우의 수를 구하는 문제이다.
입출력 조건 확인
모든 경우의 수를 다 돌면 불가능한 입출력 조건을 가지고 있다.
DP라고 부르는 연산의 결과를 저장하면서 앞으로 나아가는 방식으로 풀면 굉장히 여유롭게 풀 수 있다.
문제 풀이 내용 정리
1. 유사 피보나치
먼저 1만으로 이루어진 암호문을 예로 들어 직접 경우의 수를 구해봤다.
결과는 피보나치 수열과 동일했다.
| 1 | 11 | 111 | 1111 | 11111 | ⋯ |
|---|---|---|---|---|---|
| 1 | 3 | 5 | 8 | 13 | ⋯ |
여기에 추가로 예시로 주어진 25114를 직접 경우의 수를 구해봤다.
| 2 | 25 | 251 | 2511 | 25114 | ⋯ |
|---|---|---|---|---|---|
| 1 | 2 | 2 | 4 | 6 | ⋯ |
앞의 두 자리를 더하는 기본 원리는 동일한데, 영문자의 범위(26)를 넘어가는 숫자(51)가 나오면 경우의 수가 그대로 유지되었다.
따라서 앞의 두 자리를 더하면서 경우의 수를 확인해 나가되, 영문지의 범위를 넘어서는 숫자 두 자리가 나오면 더하지 않고 이전 숫자를 그대로 유지하면 된다.
2. 0 예외처리
위와 같이 코드를 짜게 되면 아주 쉽고 간단하게 예제 입력을 통과할 수 있다.
하지만 그대로 제출했다가는 낭패를 볼 수 있는데, 바로 0에 대한 처리가 필요하기 때문이다.
맨 앞에 0이 있네?
A가 1부터 시작하므로 맨 앞에 0이 있는 암호문은 잘못 만들어진 암호문이다.
중간에 0이 있네?
10(J), 20(T)은 존재하지만 30은 있을 수 없다.
따라서 0 앞에 3 이상의 숫자가 오는 경우에는 잘못 만들어진 암호문이다.
또한 10과 20의 경우에도 그 뒤에 추가로 숫자가 오게 된다면 그 숫자는 앞에 0이 오게 되어 경우의 수를 늘릴 수 없다.
3. 오버플로우
5000자리의 문자가 올 수 있으므로 굉장히 큰 경우의 수를 만들어 내기 때문에 문제는 출력을 100만으로 나누어 출력할 것을 요구한다.
하지만 출력값이 되기 한참 전에도 이미 long의 범위를 아득히 넘어가서 음수 양수가 번갈아가면서 나오는 오버플로우의 향연을 볼 수 있다.
따라서 이에 대한 처리를 해주어야 하는데, 어차피 100만의 나머지를 검증하기 때문에 그냥 계속 100만으로 나머지 연산을 한 값으로 수열을 구해나가면 된다.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String encrypted = sc.nextLine();
Queue<Long> qu = new LinkedList<>();
qu.offer((long) 1);
qu.offer((long) 1);
int index = 0;
long tmp, tmp2;
long result = 1;
// 0으로 시작하면 해석 불가능
if (encrypted.charAt(0) == '0') {
System.out.println(0);
} else {
for (int i = 1; i < encrypted.length(); i++) {
index = Integer.parseInt(encrypted.substring(i - 1, i + 1));
// 00일 경우 해석 불가능
if (index == 0) {
result = 0;
break;
}
// 맨 끝 두 자리가 10으로 나누어 떨어지면서 26이 넘는 경우 해석 불가능
if (i - 1 > encrypted.length() - 2) {
if (index % 10 == 0) {
if (index > 26) {
result = 0;
break;
}
// 26이 넘지 않으면 해석 가능
qu.poll();
result = qu.poll();
continue;
}
}
// 10으로 나누어 떨어지면 경우의 수가 증가하지 않으니 패스
if (i <= encrypted.length() - 2 && Integer.parseInt(encrypted.substring(i, i + 2)) % 10 == 0) continue;
// 10으로 나누어 떨어지면서 30이 넘는 경우 해석 불가능
if (index % 10 == 0) {
if (index >= 30) {
result = 0;
break;
}
// 10으로 나누어 떨어지면 경우의 수 유지
tmp = qu.poll();
qu.poll();
qu.offer(tmp);
qu.offer(tmp);
continue;
}
// 앞 자리가 0이면 경우의 수 변동 없음
else if (index < 10) continue;
// 큐 비우기
tmp = qu.poll();
tmp2 = qu.poll();
// (n - 1) + (n - 2), (n - 1) 이 두 값을 큐에 넣기
// + 쉽게 Long 범위를 벗어나서 오버플로우가 발생하니 그냥 계속 나머지 연산 돌리기
qu.offer(index <= 26 ? (tmp + tmp2) % 1000000 : tmp);
qu.offer(tmp % 1000000);
result = qu.peek();
}
System.out.println(result);
}
}
}
코드 문제점 및 해결 방법
반례 지옥 ON
| 제출 번호 | 아이디 | 문제 | 결과 | 메모리 | 시간 | 언어 | 코드 길이 |
|---|---|---|---|---|---|---|---|
| 82920186 | hcbak | 2011 | 맞았습니다!! | 18580 KB | 212 ms | Java 15 / 수정 | 1987 B |
| 82919128 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1962 B | ||
| 82918820 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1950 B | ||
| 82918799 | hcbak | 2011 | 컴파일 에러 | Java 15 / 수정 | 1951 B | ||
| 82918765 | hcbak | 2011 | 컴파일 에러 | Java 15 / 수정 | 1952 B | ||
| 82917634 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1702 B | ||
| 82917611 | hcbak | 2011 | 컴파일 에러 | Python 3 / 수정 | 1702 B | ||
| 82917362 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1517 B | ||
| 82917263 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1517 B | ||
| 82916787 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1398 B | ||
| 82916687 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 1382 B | ||
| 82915869 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 782 B | ||
| 82914928 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 760 B | ||
| 82914836 | hcbak | 2011 | 틀렸습니다 | Java 15 / 수정 | 702 B |
쉽게 생각했는데 처음 부터 맞았습니다!! 까지 코드 길이가 그라데이션으로 올라간다.
예외 케이스를 정말 많이 생각해야 했다.
퍼센트가 올라가다가 멈추고 틀렸습니다!! 나오면 뭐가 더 있을까 고민하다가 수정하고 올리면 조금 더 올라가다가 멈추고 틀렸습니다!! 반복…
마지막에는 더 이상 도저히 못찾겠어서 질문 게시판에 돌아다니는 반례란 반례는 모조리 가져다가 입력해봤다. ㅋㅋ
지저분하게 완성한 코드
결국 풀어내기는 했는데 예외처리 부분이 코드가 정말 더러워졌다.
하지만 중간부터 너무 스트레스를 받아서 일단 돼라 하고 코드를 막 집어 넣은 탓에 어떤 용도의 코드인지 잊어버려서 쉽게 수정할 수 없는 코드가 탄생했다.
앞으로는 어떤 코드를 입력할 때 어떤 용도로 어떻게 입력했는지 주석으로 작성하는 과정이 필요해 보인다.
사실 쉬워보여서 한번 큐로 해볼까? 해서 큐로 돌렸는데 아무리 생각해도 두 칸 짜리 배열로 작업하는 것이 더 간결하게 코드를 짤 수 있었을 것 같다.
어쨌든 지금은 코드를 건들지 않고자 한다. ㅋㅋ