[BOJ-2661] 좋은 수열

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

2661번: 좋은수열

---

[풀이]

나쁜 수열 123123 (123 123 인접)

나쁜 수열 11 (1 1 인접)

좋은 수열 1231

 

12323 인경우에는 23 23이 인접이 되어있기 때문에 나쁜 수열이다.

나쁜수열은 즉 인접한 부분이 동일한 패턴인 것을 뜻한다.

 

그리고 여기서 가장 좋은건 가장 작은 수를 찾아야한다.

즉 먼저 N에 도달하는 숫자를 출력하면된다.

나는 N에 도달하게되면, 재귀호출을 그만하도록 하는 변수 isStop을 만들었다.

그리고 isStop이 True이면 리턴함수를 호출하여 재귀호출을 종료하는 식으로 했다.

 

다음자리수 backtracking 하기전에 숫자(1,2,3)을 넣었을 때

동일한 패턴이 있는지 확인하는 함수 isSatisfy()를 넣었다.

 

[1] backtracking(1, '1')

패턴 구분자는 1 ~ 2/2(1) 까지이다.

=> (2, '11') , (2,'12'), (2,'13') 이 안전한 문자열인지 확인

 

 

11=> (패턴구분자: 1) nums[2-(1*2) : 2-1] ==nums[2-1 : 2] (nums[0:1]==nums[1:2]) 이므로 나쁜 문자열이다.

(2,'12'), (2, '13')은 안전한 문자열이다.

 

[2] backtracking(2,'12')

패턴 구분자는 1 ~3/2(1) 까지이다.

=> (3,'121'), (3,'122'), (3,'123') 이 안전한 문자열인지 확인

(3,'121')과 (3,'123')은 안전한 문자열이다.

 

[3] backtraking(3,'121')

패턴구분자는 1~4/2(2) 까지이다.

=> (4, '1211'), (4, '1212'), (4, '1213')이 안전한 문자열인지 확인

 

1211=>(패턴구분자: 1) nums[4-1 : 4] ==nums[4-(1*2) : 4-1] (nums[3:4]==nums[2:3]) 이므로 나쁜문자열이다.

1212=>(패턴구분자: 2) nums[4-2 : 4] ==nums[4-(2*2) : 4-2] 은 나쁜 문자열이다.

---

[코드]

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=0
ans=0
isStop=False

#동일한 패턴이 존재하는가?
def isSatisfy(n, nums):
    for i in range(1, (n//2)+1):        
        if nums[n-(i*2):n-i] == nums[n-i:]:
            return False
    return True


def backtracking(n, nums):
    global N, ans, isStop
    if isStop:
        return
    
    if n==N:
        ans= int(nums)
        isStop=True
        
    else:
        for i in range(1,4):
            #똑같은 패턴이 존재하지 않은 숫자인가?
            if (isSatisfy(n+1, nums+str(i))):
                backtracking(n+1, nums+str(i))
                    
def main():
    global N, ans
    N=int(input())
    backtracking(n=1, nums='1')
    print(ans)

if __name__=='__main__':
    main()

---

[실패 코드]

- N=7까지는 정상적으로 잘나온다

- 숫자가 점점 커질수록 느리다. (시간초과)가 떠버렸다 ㅠ

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=0
ans=float('inf')
def backtracking(n, nums):
    global N, ans
    if n==N:
        ans=min(ans,int(nums))
        
    else:
        for i in range(1,4):
            #nums의 마지막 숫자와 i가 서로 다른숫자인가?
            if str(i)!=nums[-1]:
                #똑같은 패턴이 존재하지 않은 숫자인가?
                if n>=3:
                    tmp=nums+str(i)
                    if tmp[:(n+1)//2]!=tmp[(n+1)//2:]:
                        backtracking(n+1, nums+str(i))
                else:
                    backtracking(n+1, nums+str(i))
                    
def main():
    global N, ans
    N=int(input())
    #backtracking한다.
    backtracking(n=1, nums='1')

    #ans중 가장 작은 숫자를 찾는다.
    print(ans)

if __name__=='__main__':
    main()