[BOJ, Swift] 16953 - A → B ( with DP, Greedy )

16953번: A → B

주어진 A값의 뒤에 1을 붙이거나 A를 2배하여 B로 도달하게 만드는 연산 횟수의 최솟값을 구하는 문제다.

 

요새 동적 계획법 연습을 많이 하기도 했고, 최근 푼 문제인 25418 - 정수 a를 k로 만들기가 동적 계획법으로 해결할 수 있는데, 이 문제와 결이 비슷하다고 생각하여 접근하였다가 메모리 초과가 나왔다.

 

그도 그럴 것이 B의 최댓값이 10^9 이므로 배열에 담기엔 너무 큰 수이긴 했다. (+ 동적 계획법은 배열에 일부 최적해를 계산해서 담는 방식인데, 작성한 코드를 보니 최적해를 계산한다기보단 그저 값을 할당하는 과정일 뿐이였다.)

1. DP

let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }

var (A, B) = (input[0], input[1])
var dp = Array(repeating: 0, count: B + 1)

for i in A + 1 ... B {
	// 맨 뒤 숫자가 1이고 그 전 값이 A보다 크면 +1
    if i % 10 == 1 && i / 10 >= A {
        dp[i] = dp[i / 10] + 1
    
    // 2로 나누어떨어지고 그 전 값이 A보다 크면서 값이 존재할 때 +1
    } else if i % 2 == 0 && i / 2 >= A && dp[i / 2] != -1 {
        dp[i] = dp[i / 2] + 1
    
    // 해당되지 않으면 값이 존재하지 않으므로 -1 삽입
    } else {
        dp[i] = -1
    }
}

// -1일 때는 그냥 출력하지만, 값이 있을 때는 최솟값에 +1을 하여 출력한다
dp[B] != -1 ? print(dp[B] + 1) : print(dp[B])

2. 그리디

import Foundation

let input = readLine()!.split { $0 == " " }.map { Int(String($0))! }
var (A, B) = (input[0], input[1])

// 최솟값 +1 이므로 초기화 값은 1
var ans = 1

while A != B {
    ans += 1
    let now = B
    
    // 만약 B가 1로 안끝나거나 2로 나누어떨어지지 않으면 말이 안됨.
    if B % 10 == 1 {
        B /= 10
    } else if B % 2 == 0 {
        B /= 2
    }
    
    // 위 조건문에 해당하지 않으면 -1 출력
    if now == B {
        print(-1)
        exit(0) // 없으면 바로 끝냄
    }
}

// 원하는 결과에 도달했으니 ans 출력
print(ans)