gold5-14226.md

Baekjoon

이모티콘

• 분류: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색
• 풀이 언어: Swift
• 문제 요약: 복사, 붙여넣기, 삭제의 3가지 연산만 사용해서 이모티콘을 S개로 만들기 위해 필요한 시간의 최솟값을 출력

코드

let max = Int(1e3) + 1
var queue: [(cnt: Int, cbd: Int)] = [(1, 0)]

var visit = [[Bool]](repeating: [Bool](repeating: false, count: max), count: max)
visit[1][0] = true
var indx = 0
var dur = 0

func solution(_ s: Int) -> Int {
    while indx < queue.count {
        for i in indx..<queue.count {
            let emoji = queue[i]
            if emoji.cnt == s {
                return dur
            }
            // 삭제
            if 1 < emoji.cnt - 1 && !visit[emoji.cnt - 1][emoji.cbd] {
                queue.append((emoji.cnt - 1, emoji.cbd))
                visit[emoji.cnt - 1][emoji.cbd] = true
            }
            // 복사
            if !visit[emoji.cnt][emoji.cnt] {
                queue.append((emoji.cnt, emoji.cnt))
                visit[emoji.cnt][emoji.cnt] = true
            }
            // 붙여넣기
            if emoji.cnt + emoji.cbd < max && !visit[emoji.cnt + emoji.cbd][emoji.cbd] {
                queue.append((emoji.cnt + emoji.cbd, emoji.cbd))
                visit[emoji.cnt + emoji.cbd][emoji.cbd] = true
            }
            indx += 1
        }
        dur += 1
    }
    return dur
}

let s = Int(readLine()!)!
print(solution(s))

• 메모리: 63944 KB
• 시간: 12 ms

회고

• 최근 풀었던 숨바꼭질 시리즈와 비슷한 문제라 쉽게 풀릴 줄 알았는데 예상 외로 애를 먹었다. 처음에는 방문 여부를 1차원 배열로 두고 풀어 정답이 나오지 않았는데 2차원 배열로 바꿔 화면에 있는 이모티콘의 개수와 클립보드에 있는 이모티콘의 개수를 모두 고려해주자 올바른 답이 나왔다.