[Java] 백준 31804 - Chance!

https://www.acmicpc.net/problem/31804

---

풀이

처음에는 그리디 문젠가? 했는데 그건 아니었고 dp 문제였다.

찬스를 사용한 경우와 사용하지 않은 경우 둘로 나눠서 dp 배열을 채워주면 된다.

 

i = 점수

dp[i][0] = 찬스를 아직 사용하지 않았을 때

dp[i][1] = 찬스를 이미 사용했을 때

 

dp[i][0]을 채우기 위해서는 dp[i - 1][0], dp[i / 2][0]의 값을 살펴보고

dp[i][1]을 채우기 위해서는 dp[i - 1][1], dp[i / 2][1], dp[i / 10][0]의 값을 살펴본다.

 

주의할 점은 i가 2의 배수인지도 확인해야 한다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	private static final int INF = 1000005;

	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());
		int[][] dp = new int[b + 1][2];

		for (int i = 0; i <= b; i++) {
			dp[i][0] = INF; // chance 안 씀
			dp[i][1] = INF; // chance 씀
		}

		dp[a][0] = 0;

		for (int i = a + 1; i <= b; i++) {
			if (i % 2 == 0) {
				dp[i][0] = Math.min(dp[i - 1][0] + 1, dp[i / 2][0] + 1);
				dp[i][1] = Math.min(dp[i - 1][1] + 1, dp[i / 2][1] + 1);
				if (i % 10 == 0) {
					dp[i][1] = Math.min(dp[i][1], dp[i / 10][0] + 1);
				}
			} else {
				dp[i][0] = dp[i - 1][0] + 1;
				dp[i][1] = dp[i - 1][1] + 1;
			}
		}

		System.out.println(Math.min(dp[b][0], dp[b][1]));
		br.close();
	}
}

 

---

테스트 케이스

// case 1:
1 12
ans: 3

// case 2:
1 1
ans: 0

// case 3:
2 30
ans: 2