[BOJ] 백준_16953번_A → B_C/C++백준 알고리즘2022. 2. 2. 10:00
목차
문제 출처
https://www.acmicpc.net/problem/16953
문제 설명
코드
//[BOJ] 16953번 A → B
#include<iostream>
#include<algorithm>
using namespace std;
int num = 10000;
int cnt = 1;
int dfs(long long a, long long b, int cnt)
{
if (a > b && num == 10000)
return -1;
else if (a > b)
return num;
else if (a == b)
num = min(num, cnt);
dfs(a*2, b, cnt+1);
dfs(a*10+1, b, cnt+1);
}
int main()
{
long long a, b;
cin >> a >> b;
cout << dfs(a, b, cnt)<< endl;
return 0;
}
풀이 과정
num이라는 정수형 변수로 횟수 값을 임의로 높게 잡아 설정한다. long long 타입으로 a, b 두 수를 입력받는다. a, b, cnt(연산 횟수 전역 변수)를 매개 변수로 넘기고 dfs를 돌린다. 이때 조건은 3가지가 있다. 먼저 a == b 의 경우 a가 2를 곱하거나 1을 오른쪽에 추가하는 등의 연산을 처리해서 b와 같은 값이 되었을 경우이다. 유일하게 return이 없으며 num을 num과 cnt 중 작은 값으로 설정한다. num은 초기에 10000으로 설정되어 있으므로 실질적으로 cnt 값이 num으로 들어간다. 세 가지 조건문 중 a == b 의 경우는 목적을 달성하였으므로 연산 횟수를 조정한다. 이후 또 dfs문에 a를 2 곱하는 경우와 a의 가장 오른쪽에 1을 추가하는 경우 두 가지를 모두 실행시킨다. 다른 한 경우는 a > b일 경우인데 이 경우는 a == b 의 경우 바로 다음 회차에 일어날 것이다. 때문에 임의 값에서 계속 조정된 횟수 값인 num을 리턴한다. 이 경우가 답을 출력하는 경우가 될 것이다. 또 a > b && num == 10000의 경우에는 num이 한 번도 조정되지 않았을 경우이고 이 말은 경우의 수를 초기 num 값인 10000을 넘겨서 생각해도 a를 b로 만들 수 없다는 경우이다. 이 경우에는 -1을 리턴한다.
728x90
반응형
LIST
'백준 알고리즘' 카테고리의 다른 글
[BOJ] 백준_2012번_등수 매기기_C/C++ (6) | 2022.02.27 |
---|---|
[BOJ] 백준_2810번_컵홀더_C/C++ (0) | 2022.02.26 |
[BOJ] 백준_1543번_문서 검색_C/C++ (0) | 2022.01.31 |
[BOJ] 백준_2847번_게임을 만든 동준이_C/C++ (0) | 2022.01.27 |
[BOJ] 백준_1260번_DFS와 BFS_C/C++ (0) | 2022.01.26 |
@kdj :: Childev'note
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!