https://www.acmicpc.net/problem/16953
문제
> 정수 A를 B로 바꾸려고 한다.
> 가능한 연산은 다음과 같은 두 가지이다.
1. 2를 곱한다.
2. 1을 수의 가장 오른쪽에 추가한다.
> A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.접근
큐에 계산된 수, 계산횟수를 쌍으로 하여 처리한다.
처음엔 A,0으로 큐에 넣고 얘를 통해 다음 큐에 Ax2,1와 Ax10+1,1을 넣어준다.
오른쪽에 1을 추가한다는 건 자릿수를 하나 늘려 1을 더해준것과 같기 때문에 x10+1해주면 된다.
이제 큐에 들어온 연산 결과들을 하나씩 검증한다.
그 수가 B보다 크면 볼 필요가 없기 때문에 continue;로 처내주고 만약 그 수가 B와 같다면 문제에서 횟수를 +1하라고 했으므로 return 지금 까지의 횟수 +1해준다.
만약 이 조건에 걸리지 않고 while문이 끝났다면 B가 만들어질 수 없기 때문에 -1을 리턴해준다.
문제해결
> 연산을 하는 과정을 AtoB라는 메소드로 정의해준다.
> 입력으로 수와 횟수를 받고 이를 큐의 초기값으로 pair해서 넣어준다.
> 들어온 수가 B보다 큰지, 같은지를 검사해 각각의 따른 결과를 낸다.
> 아니라면 다음 연산을 한다. 들어온 수 num에 x2와, x10+1을 해주고 큐에 넣어주면서 횟수인 rst를 +1회 해준다.
> 중간에 답이 나오면 return rst+1로 결과를 내주고 만약 여기에 걸리지 않으면 while문이 끝까지 돌아 -1을 결과로 낸다.
> 큐를 사용해 너비우선으로 탐색했으므로 num == B에 가장 먼저 걸리는 rst가 최소값이다.코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <climits>
using namespace std;
long long A, B;
long long AtoB(long long start, int rst)
{
queue<pair<long long, long long>> q;
q.push({ start, rst });
while (!q.empty())
{
long long num = q.front().first;
int rst = q.front().second;
q.pop();
if (num > B) continue;
if (num == B) return rst + 1;
q.push({ num * 2, rst + 1 });
q.push({ num * 10 + 1, rst + 1 });
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> A >> B;
cout << AtoB(A, 0) << '\n';
}
후기
모든 자료형을 int로 주고 해서 틀렸다.
문제의 범위에서 A,B가 1부터 10억까지래서 일단 생각해봤을 땐
연산의 결과가 B가 나와야 하는 문제니까 10억까지만 나오겠지 하고 했다.
근데 틀리고 생각해보니 코드 구조상 일단 큐에 연산한 수를 넘기고 거기서 B보다 큰지, 같은지를 검사해서 쳐낸다.
따라서 만약 B가 10억이고 A가 9억9천이면 큐에 99억9천..1이 들어가고, 19억8천...이 들어가서 int로는 감당이 안된다.
