문제설명
- x에 n을 더합니다
- x에 2를 곱합니다.
- x에 3을 곱합니다.
이거 3개 잘 조율해서 x를 y로 최소한의 연산을 거쳐서 바꾸면 된다고 한다 !
문제 접근
enum solveLogic {
case addition
case double
case threeple
func execute(_ x: Int, _ y: Int, _ n: Int) -> Int {
switch self {
case .addition:
return x + n
case .double:
return x * 2
case .threeple:
return x * 3
}
}
}먼저 이전에 배운 enum활용해서 여기에 로직을 한 번 넣은채로 시작을 해봤다.
이전에 순간이동? 문제에서 했듯이 뒤에서부터 역으로 연산을 해주면서 도달하게 해줘야하나?도 생각이 들었고, 근데 n이 너무 크면 어떡하지? 3배랑 n을 비교해줘야하나? 싶기도 하면서 백트래킹으로 접근을 해야겠다고 처음엔 생각이 들었다.
뒤에서부터 역으로 연산하면서, 백트래킹으로 해보자 !
뒤에서 부터 계산할거니까 다시 로직을 거꾸로 바꿔줬다(y기준으로)
enum solveLogic {
case addition
case double
case threeple
func execute(_ x: Int, _ y: Int, _ n: Int) -> Int {
switch self {
case .addition:
return y - n
case .double:
return y % 2 != 0 ? -1 : y/2
case .threeple:
return y % 3 != 0 ? -1 : y/3
}
}
}그런데 이게 여기에서 이렇게 다 판단해주니까 재귀하면서 백트래킹하려면 다 일일히 계산한 뒤에 해줘야하는 불상사가 생겨서 전면폐기를 진행했다..
깔끔하게 재귀함수 선언하고 if문으로 단순화 해주니까 생각보다 코드가 간결해졌다.
import Foundation
func solution(_ x: Int, _ y: Int, _ n: Int) -> Int {
var min_count = Int.max
func recursive(_ currentValue: Int, _ count: Int) {
if currentValue < x {
return
}
if currentValue == x {
min_count = min(min_count, count)
return
}
if currentValue % 2 == 0 {
recursive(currentValue/2, count+1)
}
if currentValue % 3 == 0 {
recursive(currentValue/3, count+1)
}
recursive(currentValue - n, count+1)
}
recursive(y, 0)
return min_count
}풀이 설명
순간이동 문제 처럼 도착지점에서부터 역으로 계산을 하되, 딱 짤라서 나눠지는거만 나눠주면서 재귀를 반복하면 안되는 애들은 중간에 떨어져나갈 것이고, 카운트로 최솟값을 가려내주면 된다 !
오류
테스트 3
입력값 〉 2, 5, 4
기댓값 〉 -1
실행 결과 〉 실행한 결괏값 9223372036854775807이 기댓값 -1과 다릅니다.
만들 수 없을 때에 대한 처리를 안해줬구나 !
그냥 Int.max값과 같으면 그거는 -1 처리를 해주면 될 것이다.
return min_count
이 코드를 아래로 변경
return min_count == Int.max ? -1 : min_count결과
테스트 10 〉 실패 (시간 초과) 테스트 11 〉 실패 (시간 초과) 테스트 12 〉 통과 (0.01ms, 16.5MB) 테스트 13 〉 통과 (0.01ms, 16.5MB) 테스트 14 〉 실패 (시간 초과) 테스트 15 〉 실패 (시간 초과) 테스트 16 〉 실패 (시간 초과) 채점 결과 정확성: 50.0 합계: 50.0 / 100.0
야무지게 시간초과가 떴다. 당장 생각 나는건 같은 값을 지나올 때는 이걸 메모를 해줘야하나 생각이 들었다.
import Foundation
func solution(_ x: Int, _ y: Int, _ n: Int) -> Int {
var min_count = Int.max
var memo = [Int: Int]()
func recursive(_ currentValue: Int, _ count: Int) {
if currentValue < x {
return
}
if currentValue == x {
min_count = min(min_count, count)
return
}
if let memoValue = memo[currentValue], memoValue <= count {
return
}
memo[currentValue] = count
if currentValue % 2 == 0 {
recursive(currentValue/2, count+1)
}
if currentValue % 3 == 0 {
recursive(currentValue/3, count+1)
}
recursive(currentValue - n, count+1)
}
recursive(y, 0)
return min_count == Int.max ? -1 : min_count
}로직 중간에 memoValue를 추가해서 이게 현재 카운팅이 더 적으면 스킵해줄 수 있도록 조건을 하나 추가해줬다.
채점 결과
정확성: 100.0
합계: 100.0 / 100.0
완성코드
import Foundation
func solution(_ x: Int, _ y: Int, _ n: Int) -> Int {
var min_count = Int.max
var memo = [Int: Int]()
func recursive(_ currentValue: Int, _ count: Int) {
if currentValue < x {
return
}
if currentValue == x {
min_count = min(min_count, count)
return
}
if let memoValue = memo[currentValue], memoValue <= count {
return
}
memo[currentValue] = count
if currentValue % 2 == 0 {
recursive(currentValue/2, count+1)
}
if currentValue % 3 == 0 {
recursive(currentValue/3, count+1)
}
recursive(currentValue - n, count+1)
}
recursive(y, 0)
return min_count == Int.max ? -1 : min_count
}타인의 코드
import Foundation
func solution(_ x:Int, _ y:Int, _ n:Int) -> Int {
let inf = 99999999
var counter: [Int: Int] = [x: 0]
for i in x...1000000 {
if let c = counter[i] {
counter[i + n] = min(counter[i + n, default: inf], c + 1)
counter[i * 2] = min(counter[i * 2, default: inf], c + 1)
counter[i * 3] = min(counter[i * 3, default: inf], c + 1)
}
}
return counter[y] ?? -1
}이분은 찐 DP로 푸신것을 볼수가 있었다. 바텀-업 방식으로 그냥 1000000까지 다 메모해주면서 엄청 쉽게 풀린듯하다. 1000000보다는 y+1 정도까지 해주면 더 최적화될 듯? 싶었다. 바로 아래 코드는 이렇게 되어있더라
var arr = Array(repeating: Int.max, count: y + 1)
백만까지여서 이게 DP로 될줄을 생각안했던 것 같은데 (감으로 한 십만정도까지인줄?) 이게 훨씬 갈겨하고 쉽게 풀 수 있는 방식이니 다음엔 DP도 생각을 해놔야겠다고 생각이 들었다.
기억보단 기록을