fragment-header
fragment-markdown
홈
로그인
로그아웃
내 블로그
설정
로그인
백준 31804 (C++) Chance!
최초 업로드: 2025-10-16 11:55:58
최근 수정 시간: 2025-10-16 11:55:58
게시자: rlatjwls3333
카테고리: 백준
조회수: 8
# [Gold IV] Chance! [문제 링크](https://www.acmicpc.net/problem/31804) ## 문제 설명 <p>자료구조 시험에서 우찬이는 $a$점을 받았고, 상훈이는 우찬이보다 높은 $b$점을 받았다. 우찬이는 상훈이보다 점수가 낮아서 화가 났지만, 공부를 하나도 하지 않아서 상훈이보다 시험을 잘 볼 수는 없다는 것을 알고 있었다. 하지만 우찬이는 최소한 동점을 받고 싶었기 때문에, 자신의 수를 바꾸는 마법을 배워서 다음 3가지 마법을 사용할 수 있게 되었다.</p> <ol> <li>물 주기: 수에 물을 주면 수가 $1$ 커진다.</li> <li>밥 주기: 수에 밥을 주면 수가 $2$배가 된다.</li> <li><em>chance!</em>: 수에 <em>chance!</em>를 외치면 수가 $10$배가 된다.</li> </ol> <p>하지만 <em>chance!</em>를 외치면 목이 너무 아프기 때문에 우찬이는 <em>chance!</em> 마법을 <strong>최대 한 번만</strong> 사용할 수 있다. 그리고 마법을 사용할 때마다 팔을 이리저리 휘저어야해서 힘이 많이 들기 때문에 마법을 최소한으로 사용하고자 한다. 우찬이가 상훈이와 동점이 되도록 하려고 할 때 마법을 최소한으로 사용하도록 도와주자.</p> ## 입력 <p>첫 번째 줄에 우찬이와 상훈이의 점수 $a$와 $b$가 공백으로 구분되어 주어진다.</p> ## 출력 <p>첫 번째 줄에 $a$를 $b$로 만들기 위해 필요한 최소 마법 사용 횟수를 출력한다.</p> ## 풀이 한 방향으로만 움직이기에 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]); } ```