백준 31804 (C++) Chance!

최초 업로드: 2025-10-16 11:55:58

최근 수정 시간: 2025-10-16 11:55:58

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] Chance!

[문제 링크](https://www.acmicpc.net/problem/31804)

## 문제 설명

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

<ol>
	<li>물 주기: 수에 물을 주면 수가 $1$ 커진다.</li>
	<li>밥 주기: 수에 밥을 주면 수가 $2$배가 된다.</li>
	<li>chance!: 수에 chance!를 외치면 수가 $10$배가 된다.</li>
</ol>

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

## 입력

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

## 출력

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

## 풀이
한 방향으로만 움직이기에 DP 또는 BFS로 해결할 수 있습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int minDist[1'000'001][2];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b; cin >> a >> b;

fill(&minDist[0][0], &minDist[1'000'000][2], 1'000'000);
 minDist[a][0]=0;
 for(int i=1;i<b;i++) {
 if(i*10<=b) minDist[i*10][1] = min(minDist[i*10][1], minDist[i][0]+1);
 for(int j=0;j<2;j++) {
 minDist[i+1][j] = min(minDist[i+1][j], minDist[i][j]+1);
 if(i*2<=b) minDist[i*2][j] = min(minDist[i*2][j], minDist[i][j]+1);
 }
 }
 cout << min(minDist[b][0], minDist[b][1]);
}
```