[백준]1463_1로 만들기

문항번호: 1로 만들기

1. 문제 분석

정수 X가 사용할 수 있는 연산

1. X%3 == 0 -> X = X/3
2. X%2 == 0 -> X = X/2
3. X = X-1

2. 풀이 계획

• 입력 제한: 1<= N <= 10^6
• 출력 : 연산을 하는 횟수의 최솟값
• 풀이 방향
  1. 총 3가지의 연산이 존재.
     • divide by 3
     • divide by 2
     • minus 1

연산의 사용을 최소화하려고 한다.

BFS 알고리즘을 활용하고, 간선을 연산의 수로 생각한다면 해당 문제를 충분히 해결할 수 있을 것 같다.
-> BFS만으로 문제에 대한 해결책을 제시했을 때 시간 초과가 발생했다.

추가적인 조건을 주어야 하겠다.
9를 3으로 나눠 3이 되는 경우도 있지만,
9를 2로 나누고, -2를 하는 경우도 있고,
9에서 -6을 하는 경우도 3으로 도달할 수 있다.

즉, 이미 방문했던 노드는 더 이상 방문하지 않도록 해야 한다.

3. 계획 검증

문항 시간제한이 상당히 깐깐하다.

4. 소스 코드

import Foundation

let N = Int(readLine()!)!
var queue = [(value: Int, depth: Int)]()

var result = 0
let level = 0
queue.append((value: N, depth: level))

var checked = Array(repeating: false, count: N+1)
checked[N] = true

while true {
    let current = queue.removeFirst()
    if current.value == 1 {
        result = current.depth
        break
    }
    var nextNode = current.value / 3
    if current.value % 3 == 0 && checked[nextNode] == false {
        checked[nextNode] = true
        queue.append((nextNode, current.depth+1))
    }
    nextNode = current.value / 2
    if current.value % 2 == 0 && checked[nextNode] == false {
        checked[nextNode] = true
        queue.append((nextNode, current.depth+1))
    }
    nextNode = current.value-1
    if checked[nextNode] == false {
        checked[nextNode] = true
        queue.append((nextNode, current.depth+1))
    }
}
print(result)

5. 돌아보기

다이나믹 프로그래밍의 적용을 swift에서 적용해본 것은 처음이다.
코드가 익숙해질 때까지 반복해야겠다.
중복 방문을 막기 전에는 시간 초과가 발생했지만, 중복 발생에 대한 문제 해결 이후 시간 초과를 해결할 수 있었다.

• nextNode 라는 변수명은 추후에 수정한 부분이다.
• 의미상 해석이 좋은 네이밍으로 풀이를 진행하는 게 좋을 것 같다.

tag: problem solving  다이나믹 프로그래밍