[백준] 14226번 이모티콘

이모티콘

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	30133	11403	7622	34.481%

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

4

예제 출력 2

4

예제 입력 3

6

예제 출력 3

5

예제 입력 4

18

예제 출력 4

8

내 코드

IndexError

from collections import deque

def bfs(S):
    MAX = 1001
    visited = [False] * MAX  # 개수에 도달 했냐
    emoticon_count = 1  # 이모티콘 개수
    now_time = 0  # 경과초
    copied_count = 0  # 복사개수
    queue = deque([(now_time, emoticon_count, copied_count)])  # (경과초, 개수, 복사개수)
    visited[emoticon_count] = True
    while_break = False
    
    while queue:
        now_time, emoticon_count, copied_count = queue.popleft()
        # print('now_time, emoticon_count, copied_count:', now_time, emoticon_count, copied_count)
        now_time += 1

        for act in ('paste', 'copy', 'delete'):
            if act == 'delete' and emoticon_count > 1 and not visited[emoticon_count - 1]:
                temp_emoticon_count = emoticon_count - 1
                visited[temp_emoticon_count] = True
                queue.append((now_time, temp_emoticon_count, copied_count))
                # print(act, queue)
                if temp_emoticon_count >= S:
                    if temp_emoticon_count == S:
                        while_break = True
                    break
            elif act == 'paste' and copied_count > 0 and emoticon_count + copied_count <= 1000 and not visited[emoticon_count + copied_count]:
                temp_emoticon_count = emoticon_count + copied_count
                visited[temp_emoticon_count] = True
                queue.append((now_time, temp_emoticon_count, copied_count))
                # print(act, queue)
                if temp_emoticon_count == S:
                    while_break = True
                    break
            elif act == 'copy' and copied_count != emoticon_count:
                copied_count = emoticon_count
                queue.append((now_time, emoticon_count, copied_count))
                # print(act, queue)

        if while_break:
            break

    return now_time  # 빠져나오면 시간 반환

S = int(input())
print(bfs(S))

chatGPT

문제 해결 접근

이 문제는 BFS(너비 우선 탐색) 을 사용하여 최단 시간에 원하는 이모티콘 개수를 만들도록 해야 한다.

문제 풀이 과정

1. 상태 정의
   • 현재 화면에 있는 이모티콘 개수 (count)
   • 현재 클립보드에 저장된 이모티콘 개수 (clipboard)
   • 경과 시간 (time)
2. BFS 탐색 (최단 경로 문제이므로 BFS 적합)
   • 한 번 방문한 상태를 다시 방문하면 비효율적이므로 (count, clipboard) 상태를 방문 체크
   • 다음 3가지 연산 수행:
     • 복사 (Copy): 현재 count를 clipboard에 저장 (이전에 같은 clipboard 값이 있는 경우 중복 수행 방지)
     • 붙여넣기 (Paste): clipboard 개수를 count에 추가
     • 삭제 (Delete): count를 1 감소
3. 종료 조건
   • count == S 가 되면 즉시 종료 후 time 출력

---

개선된 코드

from collections import deque

def bfs(S):
    queue = deque([(1, 0, 0)])  # (현재 이모티콘 개수, 클립보드 개수, 경과 시간)
    visited = set()  # (현재 개수, 클립보드 개수) 상태를 저장
    visited.add((1, 0))

    while queue:
        count, clipboard, time = queue.popleft()

        if count == S:
            return time  # 최단 시간 반환

        # 1. 복사 (Copy)
        if (count, count) not in visited:
            visited.add((count, count))
            queue.append((count, count, time + 1))

        # 2. 붙여넣기 (Paste)
        if clipboard > 0 and count + clipboard <= 1000 and (count + clipboard, clipboard) not in visited:
            visited.add((count + clipboard, clipboard))
            queue.append((count + clipboard, clipboard, time + 1))

        # 3. 삭제 (Delete)
        if count > 1 and (count - 1, clipboard) not in visited:
            visited.add((count - 1, clipboard))
            queue.append((count - 1, clipboard, time + 1))

S = int(input())
print(bfs(S))

---

개선된 코드의 장점

1. 메모리 절약 (O(S^2) → O(S))
   • 원래 코드에서는 1001 크기의 방문 배열을 사용했지만,(현재 개수, 클립보드 개수) 쌍을 set()로 관리하여 메모리를 줄임.
   • 공간 복잡도가 O(S) 에 가까움.
2. 불필요한 변수 제거
   • while_break 같은 불필요한 종료 변수를 없애고 if count == S: 시 즉시 반환.
   • MAX 같은 고정 배열 대신, visited를 set()으로 관리하여 불필요한 범위 검사를 줄임.
3. BFS의 장점 유지 (O(S))
   • BFS는 최단 경로 탐색에 적합하며, 한 번 방문한 상태는 다시 방문하지 않음.
   • 시간 복잡도는 여전히 O(S) 이므로 효율적.

부가 질문

1. 복사 (Copy)
    if (count, count) not in visited:
에서 (count, count) 인 이유는?

(count, count)가 되는 이유는 "복사 (Copy)" 연산의 동작 방식 때문입니다.

---

이모티콘 복사 연산 동작

• 현재 화면에 있는 이모티콘 개수(count) 를 클립보드(clipboard)에 저장하는 연산이므로,즉 화면 개수 그대로 클립보드에 저장됩니다.
• 따라서, 현재 이모티콘 개수가 count일 때, 복사를 하면 (count, count) 상태가 됩니다.

---

예제 분석

예제: S = 6

1. 초기 상태:
   • 화면: 1개, 클립보드: 0개, 시간: 0초
   • queue = deque([(1, 0, 0)])
2. 1초 후 (복사)
   • 화면: 1개, 클립보드: 1개
   • queue.append((1, 1, 1))
   • 즉, (count, count) → (1, 1)
3. 2초 후 (붙여넣기)
   • 화면: 2개, 클립보드: 1개
   • queue.append((2, 1, 2))

---

복사를 (count, count)로 처리하지 않으면 생기는 문제

만약 (count, clipboard)로 처리하지 않고 clipboard를 유지하면,

클립보드 값이 그대로 남아 불필요한 중복 탐색이 생깁니다.

즉, BFS에서 중복된 상태를 여러 번 방문할 위험이 있습니다.

---

정리

• (count, count)가 되는 이유는 복사를 하면 화면 개수와 클립보드 개수가 동일해지기 때문입니다.
• visited에서 (count, count)를 체크하는 이유는 같은 상태를 중복 방문하지 않도록 하기 위해서입니다.

즉, "복사" 연산의 정확한 의미를 코드에 반영한 것! 🚀

내 생각

1. visited 를 생각했으나, 복사 개수가 달라지면 다른 상태라는 걸 생각 못했다.
2. for 로 delete, paste, copy 를 돌 필요 없이 (이모티콘 개수, 복사 개수) 가 있는지 검사만 하면 되었