(Python/🥇4)백준알고리즘 2661번: 좋은 수열

백준 알고리즘 좋은수열

 

문제 바로가기 

 

문제:

숫자 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들 사이에는 빈칸을 두지 않는다.

 

풀이:

 

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N = int(sys.stdin.readline())

def bt(res,cnt):
    for i in range(1, cnt//2+1):
        if str(res)[-i:] == str(res)[-i*2:-i]:
            return
    if cnt == N:
        print(res)
        exit(0)
    for i in range(1,4):
        tmp = (res*10) +i
        bt(tmp,cnt+1)

print(bt(0,0))

 

1,2,3 을 반복적으로 넣는다. 

 

인덱싱이 좀 어려웠다.

예를들어 12131213

이 수 일때 range 는 4가 나오므로 맨뒤에 1~4 까지 비교하면된다.

3과 1

13과 12

213 과131

1213과 1213 

이런식으로 그래서 인덱싱은 

오른쪽 부분은 [-i] 만큼 빼고 왼쪽 부분은 *2만큼 더 빼줘야하므로 *2를 해주면 된다.