[백준 | 골드4] : 2661 좋은수열(백트랙킹, 수열)

https://www.acmicpc.net/problem/2661

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

예제 입력 1 복사

7

예제 출력 1 복사

 

1213121

 

 

1. 1, 2, 3 배열 갖고 길이 n개 순열 만들기

2. 1, 2, 3을 반복적으로 리스트 배열에 넣고, 백트랙킹를 실행하자.
3. 최소 값으로 만들기 위해 1, 2, 3 순으로 넣는다.
4. 좋은 수열인지 확인하는 함수를 만들자(check)
5. 반복 수열이 발생하면 맨 뒤의 수를 지우고 다음 수를 넣는다.
6. check 함수를 만들 때 어떻게 비교를 하나
7. 1 ~ len(res)//2 의 범위

 

(예시)

1, 2, 3으로 길이 3만큼 순열을 만든다고 했을 때 나오는 결과물

111
112
113
121
122
123
131
132
133
211
212
213
221
222
223
231
232
233
311
312
313
321
322
323
331
332
333

 

flag로 숫자 안쳐내면 이렇게 나온다

 - 좋은 순열 목록

121
123
131
132
212
213
231
232
312
313
321
323

n = int(input())
numList = ['1', '2', '3']
result = []
flag = False

def checkGood(num) :
    for i in range(1, len(num) // 2 + 1) :
        if num[-i:] == num[-i-i:-i] :
            return False
    return True

def backDFS(L) :
    global flag

    if flag is True :
        return

    if L == n :
        flag = True
        num = "".join(result)
        print(num)
        return
    
    else : 
        for i in range(3) :
            result.append(numList[i])
            if checkGood(result) :
                backDFS(L+1)
            result.pop()

backDFS(0)