탐욕적인 사람 되기 -정수 a를 k로 만들기 문제-

1. 문제

 

25418번: 정수 a를 k로 만들기 (acmicpc.net)

25418번: 정수 a를 k로 만들기

 

 

정수 a에 1을 더하거나 2를 곱해서 k를 만들때, 연산 횟수의 최솟값을 구하는 문제

 

 

2. 풀이1(BFS)

 

이 문제의 기본은 BFS로 푸는 것이다

 

정수 a에서 시작해서, delta 배열은 1,2가 있고

 

1이 나오면 a + 1에 가서 범위를 벗어난건지, 이미 방문했는지 검사

 

2가 나오면 2a에 가서 범위를 벗어난건지, 이미 방문했는지 검사

 

from collections import deque

def bfs(a,k):
    
    queue = deque([(a,0)])

    visited = [0] * (1000001)

    visited[a] = 1

    while queue:
        
        a,c = queue.popleft()

        for o in [1,2]:
            
            if o == 1:
                
                if a + 1 <= 1000000 and visited[a+1] == 0:

                    if a+1 == k:

                        return c+1

                    else:
                        
                        visited[a+1] = 1

                        queue.append((a+1,c+1))
            
            elif o == 2:
                
                if a*2 <= 1000000 and visited[2*a] == 0:
                    
                    if 2*a == k:
                        
                        return c+1
                    
                    else:
                        
                        visited[2*a] = 1
                        queue.append((2*a,c+1))



a,k = map(int,input().split())

print(bfs(a,k))

 

 

3. 풀이2(DP)

 

다이나믹 프로그래밍으로도 풀이가 가능하다

 

어떻게 하냐면.. dp[i]를 정수 a에서 시작해서 i까지 최소 연산 횟수로 정의한다.

 

그러면 dp[a] = 0이다. 당연히 a에서 a까지는 0번의 연산으로 가능하다.

 

이제 목표는 dp[k]가 된다.

 

from sys import stdin

dp = [100000000]*(1000001)

a,k = map(int,stdin.readline().split())

dp[a] = 0

for i in range(a+1,k+1):
    
    dp[i] = dp[i-1] + 1

    if i % 2 == 0:
        
        dp[i] = min(dp[i],dp[i//2] + 1)

print(dp[k])

 

a+1부터 k까지 채워나간다.

 

정수 i로 오는 방법은 어떤 경우가 있을까?

 

먼저 i-1에서 1을 더해서 i로 오는 방법이 있다.

 

dp[i] = dp[i-1] + 1이다. 

 

당연히 i 까지 되는 최소연산 횟수는, i-1까지 최소연산으로 왔을때(dp[i-1]) 1을 더하는게 최선이다.

 

두번째로는 i//2에서 2를 곱하는 연산으로 i에 오는 방법이 있다.

 

만약에 i가 2로 나누어 떨어진다면, i//2에서 2를 곱하는 연산으로 i로 오게 된다.

 

따라서 dp[i] = min(dp[i], dp[i//2] + 1)

 

 

4. 풀이3(그리디 알고리즘)

 

문제의 특징을 잘 살펴보면, a,k는 양의 정수이고 a < k이다.

 

그리고 연산은 1을 더하거나 2를 곱하는, 무조건 앞으로만 가는 연산이다.

 

따라서 최소 연산으로 갈려면 무조건 2를 곱하는게 최선이다.

 

근데 a > k로 가면 문제가

 

7에서 77로 가고 싶을때, 무조건 2를 곱해서 14, 28, 56까지 오고 2를 곱하면 77을 넘으니까 여기서부터는 1을 더해

 

근데 이것보다는 중간 어느 지점에서 1을 더하고 2를 곱해나가면 최소로 가는 경우가 생긴다

 

7에서 1을 더해서 8

 

1 더해서 9

 

2 곱해서 18

 

1 더해서 19

 

2 곱해서 38

 

2 곱해서 76

 

1 더해서 77

 

그러니까 k에서 a로 역으로 가는 방법을 생각한다

 

2로 나눌 수 있으면 무조건 2로 나눈다

 

그런데 2로 나눈 값이 a보다 작아지면 더 이상 나누지 않고 거기서부터는 1을 빼준다

 

그러다가 a에 도달하면 그것이 연산 횟수의 최솟값

 

from sys import stdin

a,k = map(int,stdin.readline().split())

answer = 0

while k != a:
    
    if k % 2 == 0:

        if k//2 < a:
            
            break
        
        k = k//2
    
    else:
        
        k -= 1
    
    answer += 1

print(answer + (k-a))