goodseq

문제

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

 

예제 입력

7

예제 출력

1213121

 

#코드

import sys
 
def getResult(x):
  # result[x]를 결정한 후, result[x+1]부터 쭉 결정해 나가는 함수.
  # result[x] ~ result[n-1]까지 결정하는 함수
  
  # (1) x번째 숫자를 결정한다.
  # (2) x+1번째 숫자를 결정하러 간다 --> getResult(x+1)
  
  # 0 1 2 3 4 5 6 7    8 getResult(8)
  # 1 2 1 3 1 2 3 1    ?
  
  # 1을 넣어본다. 괜찮은지 확인한다. 괜찮다면 getResult(x+1) --> 안괜찮음
  # 2를 넣어본다. 괜찮은지 확인한다. 괜찮다면 getResult(x+1) --> 안괜찮음
  # 3을 넣어본다. 괜찮은지 확인한다. 괜찮다면 getResult(x+1)
  
  # 8번째? 2가능여부 체크
  # 1      2
  # 2 3    1 2
  # 3 1 2  3 1 2 (불가능)
  global result, resultLen, exit
  if exit == True: return
  # 기저 조건
  if x >= n:
    for i in range(n):
      print(result[i], end='')
    exit = True
    return
  else:
    for i in range(1, 4):
      result[x] = i
      flag = False
      for j in range(1, ((x+1)//2)+1): # 가능여부 범위체크 
        if isPossible(x, j) == False: # 중복이 안되면 True, 중복이 되면 False 반환
          flag = True
          break
      # 가능한지 체크, 가능하다면 getResult(x+1)
      if flag == False: # 가능
        getResult(x+1)
        
#isPossible(7, 3) : idx 7이 맨끝이고, 구간 3         
def isPossible(x, length):
  # result[x]가 오른쪽 끝이고, 길이 length의 중복이 있는지 판별.
  # 중복이 없다면 True, 있다면 False
  for i in range(length):
    if result[x-i] != result[x-i-length]:
      return True
  return False    
  
if __name__ == '__main__':
  result = [0 for _ in range(100)]
  resultLen = 0
  n = int(sys.stdin.readline())
  exit = False
  
  getResult(0) # result[0] ~ reesult[n-1]까지 결정