[백준 31804] Chance! - Java 문제풀이

문제 링크: https://www.acmicpc.net/problem/31804

 

 

문제

자료구조 시험에서 우찬이는 a점을 받았고, 상훈이는 우찬이보다 높은 b점을 받았다. 우찬이는 상훈이보다 점수가 낮아서 화가 났지만, 공부를 하나도 하지 않아서 상훈이보다 시험을 잘 볼 수는 없다는 것을 알고 있었다. 하지만 우찬이는 최소한 동점을 받고 싶었기 때문에, 자신의 수를 바꾸는 마법을 배워서 다음 3가지 마법을 사용할 수 있게 되었다.

1. 물 주기: 수에 물을 주면 수가 1 커진다.
2. 밥 주기: 수에 밥을 주면 수가 2배가 된다.
3. chance!: 수에 chance!를 외치면 수가 10배가 된다.

하지만 chance!를 외치면 목이 너무 아프기 때문에 우찬이는 chance! 마법을 최대 한 번만 사용할 수 있다. 그리고 마법을 사용할 때마다 팔을 이리저리 휘저어야해서 힘이 많이 들기 때문에 마법을 최소한으로 사용하고자 한다. 우찬이가 상훈이와 동점이 되도록 하려고 할 때 마법을 최소한으로 사용하도록 도와주자.

 

입력

첫 번째 줄에 우찬이와 상훈이의 점수 a와 b가 공백으로 구분되어 주어진다.

 

출력

첫 번째 줄에 a를 b로 만들기 위해 필요한 최소 마법 사용 횟수를 출력한다.

풀이

접근법

1. BFS를 이용할 수도 있지만, 단순히 수가 커지고 있기 때문에(작아지지 않음) bottom-up 방식의 dp로 접근해도 괜찮을 것 같다.
2. 각 분기를 생각하면서 조건에 따라 dp 배열을 채워준다. => 코드 각주 참고

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 14:25 ~
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        // BFS를 이용할 수도 있지만, 단순히 수가 커지고 있기 때문에(작아지지 않음) bottom-up 방식의 dp로 접근해도 괜찮을 것 같다.
        int[][] dp = new int[b+1][2];
        for(int i=0;i<=b;i++) Arrays.fill(dp[i], -1);
        dp[a][0] = 0;
        // 현재 수
        for(int i=a+1;i<=b;i++) {
            // 물주기
            dp[i][0] = dp[i-1][0] + 1;
            // 만약 이전에 chance를 외친 적이 있다면
            if (dp[i-1][1] != -1) dp[i][1] = dp[i-1][1] + 1;

            // 만약 밥을 줄 수 있다면
            if(i%2 == 0 && dp[i/2][0] != -1) {
                dp[i][0] = Math.min(dp[i][0], dp[i/2][0] + 1);
                if (dp[i/2][1] != -1) dp[i][1] = dp[i][1] == -1 ? dp[i/2][1]+1 : Math.min(dp[i][1], dp[i/2][1] + 1);
            }

            // 만약 chance를 외칠 수 있다면
            if (i%10 == 0 && dp[i/10][0] != -1) {
                dp[i][1] = dp[i][1] == -1 ? dp[i/10][0] + 1 : Math.min(dp[i][1], dp[i/10][0] + 1);
            }
        }
        int ans = 0;
        if (dp[b][0] != -1 && dp[b][1] != -1) ans = Math.min(dp[b][0], dp[b][1]);
        else ans = Math.max(dp[b][0], dp[b][1]);
        System.out.println(ans);
    }
}