좋은 수열
시간 제한1초메모리 제한128 MB
숫자 1,2,3만 사용해 인접한 같은 길이의 부분열이 반복되지 않는 좋은 수열 중 길이 N에서 값이 가장 작은 것을 구합니다.
문제
숫자 1, 2, 3만으로 이루어진 수열을 생각하자. 어떤 양의 길이에 대해 서로 이웃한 두 부분 수열이 완전히 같으면 그 수열은 나쁜 수열이다. 그런 경우가 하나도 없는 수열은 좋은 수열이다.
나쁜 수열은 다음과 같다.
3332121323(21이 바로 이어서 반복된다)123123213(123이 바로 이어서 반복된다)
좋은 수열은 다음과 같다.
232321231232123
길이가 N인 좋은 수열을 N자리 정수로 보았을 때, 그중 가장 작은 수를 나타내는 수열을 구하라. 예를 들어 1213121과 2123212는 모두 좋은 수열이지만, 더 작은 수는 1213121이다.
입력
입력은 정수 N 하나로 이루어진다. N은 1 이상 80 이하이다.
출력
첫째 줄에 1, 2, 3만으로 이루어진 길이 N의 좋은 수열 중 가장 작은 수를 나타내는 수열을 출력한다. 수열의 숫자 사이에는 공백을 넣지 않는다.