.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
문제
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
다음은 나쁜 수열의 예이다.
•
33
•
3323
2121
•
123123213
다음은 좋은 수열의 예이다.
•
2
•
32
•
32123
•
1232123
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
입력
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.
출력
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
예제 입력 1
7
Plain Text
복사
예제 출력 1
1213121
Plain Text
복사
Solution
문자열의 길이가 N과 같으면, 정답 문자열과 비교하여 작은 것을 정답 문자열로 갱신한다.
문자열의 길이가 N과 같지 않으면, 다음에 올 수 있는 수를 탐색한다. 이 때 필요한 유망성 검사는 2가지이다.
1. 가장 최근에 붙여진 수와 같은 수가 붙으면 나쁜 수열이 되므로 제외한다.
2. 끝에서부터 짝수개의 수가 서로 동일한지 검사한다.
# 문제에서 요구한 건 가장 작은 수열이고, 실제로 가장 작은 1부터 탐색하기 때문에, 첫 번째로 발견한 길이 N의 좋은 수열이 곧 답이 된다. 따라서 그 즉시 수열을 출력하고 알고리즘을 종료하면 시간 초과 문제가 해결된다.
