문제 설명

구현 아이디어 1

• 상태공간트리를 활용하여 문제를 풀자!
• 시간의 최솟값을 세기 위해 depth(그래프의 깊이를 나타내는 변수)를 사용
• screen + clip이나 screen - 1이 s가 되면 depth를 출력
  • 1번 과정은 화면에 있는 이모티콘의 수가 변하지 않으므로 고려하지 않는다
• 다음 결과를 구하는데 직전의 노드만 필요하므로, 1차원 리스트를 사용
  • ex) depth=2를 구하는데 depth=0이 필요 없음

전체 코드 1 - 메모리 초과

import sys

input = sys.stdin.readline

s = int(input())

depth = 0 # 그래프의 깊이를 나타내는 변수
flag = False # 반복문 탈출용
result = [(1,0)]

while True: # 이모티콘이 S개가 될 때까지 반복
    temp = []

    depth += 1
    for screen, clip in result:
    	# 이모티콘이 S개가 되면 반복문을 빠져나온다
        if screen + clip == s or screen - 1 == s:
            flag = True
            break
        # 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
        temp.append((screen, screen))
        # 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
        temp.append((screen+clip, clip))
        # 3. 화면에 있는 이모티콘 중 하나를 삭제한다.
        temp.append((screen-1, clip))

    if flag:
        break

    result = temp # result 리스트를 갱신

print(depth)

결과는 메모리 초과가 나왔다.

구현 아이디어 2

상태공간트리를 다시 보자.

❌ 표시를 한 노드는 또 계산할 필요가 없다.

• 이미 나온 적 있는 경우 → 연산을 한번 더 하면 걸리는 시간이 최소가 아니기 때문
• (0, 0)인 경우 → 1번이나 2번 연산을 하면 이미 나온 적 있는 경우가 됨, 3번 연산을 하면 screen이 음수가 됨

하지만, 위에서 작성한 방법으로 하게 되면 계산할 필요가 없는 노드에 대해서도 계산을 하기 때문에 무의미한 노드가 기하급수적으로 늘어나며 메모리 초과가 뜬 것이다.

그러므로 연산을 한 번 더 하는게 무의미한 노드들에 대해 예외처리를 추가하여 메모리 초과를 해결하자.

상태공간트리를 조금 더 보자.

depth가 3에서 4가 될 때, (2,2)에 주목하자.
screen = clip인 경우에도, 1번 연산을 하면 이미 나온 적 있는 노드가 되므로 고려하지 않아도 됨을 알 수 있다.

전체 코드 2 - 맞았습니다

import sys

input = sys.stdin.readline

s = int(input())

depth = 0
flag = False
result = [(1,0)]
st = set() # 이미 나온 적 있는 노드들을 저장

while True:
    temp = []

    depth += 1
    for screen, clip in result:
    	# 이모티콘이 S개가 된 경우
        if screen + clip == s or screen - 1 == s:
            flag = True
            break
        
        # 1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
        if (screen, screen) not in st and screen != clip:
            temp.append((screen, screen))
            st.add((screen, screen))

        # 2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
        if (screen+clip, clip) not in st:
            temp.append((screen+clip, clip))
            st.add((screen+clip, clip))

        # 3. 화면에 있는 이모티콘 중 하나를 삭제한다.
        if (screen-1, clip) not in st and screen > 0:
            temp.append((screen-1, clip))
            st.add((screen-1, clip))

    if flag:
        break

    result = temp

print(depth)

in 연산을 리스트에 사용하는 것보다 집합 자료형에 사용하는 것이 더 빠르기 때문에, 이미 나온 적 있는 노드를 저장할 때는 set 자료형을 사용해주었다.

• 연산을 하기 전에 st에 이미 있는지 확인하고
• (0, 0)이거나 screen == clip일 경우 연산을 하지 않도록

조건문을 추가해주었다.