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

문제 정보

---

2661번: 좋은수열

 

 

핵심

---

좋은 수열인지 검사할 때, 나는 처음에 예시로 나온 나쁜 수열의 모든 경우의 수를 계산하려고 코드를 짜고 있었다

하지만, 여기서 핵심은 수열을 만들어 나갈 때 나는 좋은 수열을 만들어 나가는 것이다

다시 말하면, 7이라는 N이 주어졌고 6개의 숫자로 이루어진 수열이 만들어졌으며 1개의 추가할 숫자가 남아있다고 한다면

내가 만들었던 길이 6을 가지는 수열은 이미 좋은 수열이기 때문에 그들 사이를 검사하려고 노력하지 않아도 된다는 것이다

 

예를 들어서 예제 입력처럼 N이 7로 주어졌을 때

#1
1

#2
12

#3
121

#4
1213

#5
12131

#6
121312

#7
1213121

해당 수열이 만들어나가는 과정 속에서도 모든 단계에서의 수열은 좋은 수열이라는 것이다

 

내가 마지막 7단계에서 굳이 이 수열을 1 2 , 2 1 , 1 3, 3 1, 1 2, 2 1 이런식으로 비교하지 않아도 된다는 말이다

우리는 단지 이 3번의 연산을 필요로 하는 것이다

 

이것때문에 나는 시간을 조금 소요하게 되었던 것 같아 적어본다

 

 

풀이

---

from sys import stdin

def dfs(N):
    global result
    if len(result) == N:
        print(''.join(str(i) for i in result))
        exit(0)
    for i in range(1, 4):
        result.append(i)
        if check(result):
            dfs(N)
        result.pop()

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

N = int(stdin.readline())
result = []
dfs(N)

DFS를 활용한 풀이이다

배열 result는 좋은 수열을 차례차례 저장하는 배열이고, 이 배열의 길이가 N이 될 때 이 배열을 출력해주고 프로그램을 종료시킨다 exit(0)

 

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

여기서 보면, 인덱스들을 잘 이해 못할수도 있지만 앞서 말한것처럼 우리는 어떤 부분수열을 검사해야하는지 알았고

 

#i=1
result[-1:] == result[-2:-1]

#i=2
result[-2:] == result[-4:-2]

#i=3
result[-3:] == result[-6:-3]

이런식으로 부분수열을 검사하면 되므로 위와 같은 코드를 작성할 수 있을 것이다

 

또한, exit(0)를 줘서 한가지 결과를 가지고 프로그램을 종료시킨 이유는

최소 합을 가지는 부분수열을 구하는 것이지만 dfs() 에서 for loop 가 진행될 때

1, 2, 3 순서대로 진행되기 때문에 (작은 수부터) 가장 먼저 완성되는 배열이 최소 합을 가지는 부분수열이라고 할 수 있다

 

 

고찰

---

exit(0) 말고도 전역변수로 T/F 값을 주어서 더이상 재귀가 반복되지 않도록 할 수도 있다!

 

참고

---

GitHub - dduneon/CodingTestPy