[Swift 알고리즘] 백준 BOJ - 1463 1로 만들기

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 1463 1로 만들기" 문제를 풀었습니다.

 

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

1463번: 1로 만들기

 

---

풀이

이번 문제는 DP 문제입니다.

 

DP는 과거의 계산 값을 이용해 현재 값을 구하는 방법이라고 생각하시면 되는데요.

이번 문제도 이런 규칙이 적용됩니다.

 

1은 0회, 2와 3은 1회입니다.

이 세 가지 기본 값을 이용해 4 이상의 값을 구해봅시다.

 

4는 4 / 2 / 2를 이용해 1로 만들 수 있습니다. 이는 2의 결과값에 나눗셈 1회를 추가로 한 연산입니다.

따라서 2의 결과값에 1을 더한 값이 4의 결과입니다.

 

9는 9 / 3 / 1을 이용해 1로 만들 수 있습니다. 이는 3의 결과값에 나눗셈 1회를 추가로 한 연산으로

3의 결과값에 1을 더한 값이 9의 결과입니다.

 

6을 볼까요? 6은 2와 3 둘 다 나누어 떨어지는 수입니다.

따라서 2의 결과값에 1을 더한 값과 3의 결과값에 1을 더한 값 중 최솟값이 6의 결과입니다.

 

7은 어떨까요? 7은 2와 3 모두 나누어 떨어지지 않습니다.

이런 경우엔 1을 뺀 값인 6의 결과값에 1을 더한 값이 7의 결과입니다.

 

마지막으로 모든 상황에 대해 -1을 뺀 값의 결과값 + 1과도 뭐가 최소인지 비교를 해주어야 합니다.

 

위 케이스에 대해 코드를 작성하면 답이 짜잔하고 나옵니다.

 

---

전체 코드

//
//  FileIO.swift
//  SwiftAlgorithm
//
//  Created by 유정주 on 2022/03/16.
//

//1463 1로 만들기
import Foundation

final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45{ isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

let file = FileIO()
let input = file.readInt()
//import Foundation
//let input = Int(readLine()!)!

var dp: [Int] = [0, 0, 1, 1]
if input >= 4 {
    for i in 4...input {
        var value = 0
        if i % 2 == 0 && i % 3 == 0 {
            value = min(dp[i/2], min(dp[i/3], dp[i-1]))
        } else if i % 2 == 0 {
            value = min(dp[i/2], dp[i-1])
        } else if i % 3 == 0 {
            value = min(dp[i/3], dp[i-1])
        } else {
            value = dp[i-1]
        }
        dp.append(value + 1)
    }
}
print(dp[input])

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.