문제:
숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.
다음은 나쁜 수열의 예이다.
- 33
- 32121323
- 123123213
다음은 좋은 수열의 예이다.
- 2
- 32
- 32123
- 1232123
길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.
입력:
입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.
출력:
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
풀이방법:
dfs를 사용해서 수열에 숫자 하나씩을 붙여나가면서 좋은 수열인지 확인하고, 좋은 수열이라면 다시 붙이고, 그렇지 않다면 다른 숫자를 붙이는 방법을 사용하도록 한다.
좋은 수열들 중 가장 작은 값을 찾아야 한다. 따라서 작은 값이 되기 위해서는 1로 시작해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import sys
def good_permutation(number):
for i in range(1,len(number)//2+1):
if number[-i:]==number[-2*i:-i]:
return False
return True
def dfs(number,idx):
if idx == n:
print(number)
sys.exit()
for c in ['1','2','3']:
if good_permutation(number+c):
dfs(number+c,idx+1)
n = int(input())
number = '1'
dfs(number,1)
|
cs |
문제링크:
2661번: 좋은수열
첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]2529. 부등호 (0) | 2021.01.26 |
|---|---|
| [BOJ]2003. 수들의 합 2 (0) | 2021.01.19 |
| [BOJ]15711. 환상의 짝꿍 (0) | 2021.01.12 |
| [BOJ]14938. 서강그라운드 (0) | 2021.01.07 |
| [BOJ]1922. 네트워크 연결 (0) | 2021.01.05 |