[ BOJ / C++ ] 16953번 A → B
이번 문제는 DFS 알고리즘을 재귀적으로 구현하여 해결했다.
- 정수A를 2로 곱할 수도 있고, 10을 곱한 뒤에 1을 더할 수도 있다.
- DFS 함수 안에서 x2와 x10+1을 DFS로 재귀호출 한다.
- result에는 임의의 큰 값을 넣고, result에는 더 작은 cnt값이 들어간다.
- result가 마지막에도 임의의 큰 수라면 A가 B로 될 수 없다고 판단하고 -1을 출력한다.
Code
#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
long long a, b;
long long cnt=1;
long long result=MAX;
void Input(){
cin>>a>>b;
}
void DFS(long long n, long long cnt){
if(n==b){
result=min(cnt, result);
}
if(n>b)
return;
DFS(n*2, cnt+1);
DFS((n*10)+1, cnt+1);
}
void Solution(){
DFS(a, cnt);
if(result==MAX){
cout<<-1<<endl;
}
else{
cout<<result<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
return 0;
}
#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
long long a, b;
long long cnt=1;
long long result=MAX;
void Input(){
cin>>a>>b;
}
void DFS(long long n, long long cnt){
if(n==b){
result=min(cnt, result);
}
if(n>b)
return;
DFS(n*2, cnt+1);
DFS((n*10)+1, cnt+1);
}
void Solution(){
DFS(a, cnt);
if(result==MAX){
cout<<-1<<endl;
}
else{
cout<<result<<endl;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution();
return 0;
}
이번에 또 수의 범위를 신경쓰지 않고 int형으로 사용했다가 오답처리를 당했다. 수의 범위를 신경쓰며 구현하자.
Author And Source
이 문제에 관하여([ BOJ / C++ ] 16953번 A → B), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-C-16953번-A-B저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)