[BOJ][Silver II] 15663번: A -> B
문제
접근 방법
두 개의 연산이 정의됨.
- 2를 곱하기 ( *2 )
- 1을 수의 가장 오른 쪽에 추가 (*10+1)
이 두 개의 연산으로 A를 B로 만드는데 드는 최소 연산 값을 찾으면 된다.
그러면 A에다가 1을 몇 번 추가하고, 2를 몇 번 곱하면 B가 나온다는 얘기인데, A->B의 과정에서는 언제 1을 더하고 2를 곱해야 하는지 확실하지 않을 때가 많다.
그러면 이렇게 생각해보자. A에서 B를 가는 과정은 불확실하다. 그러나 A->B의 과정이 된다고 가정하면, 두 연산만으로 A가 B에 도달하는 한 가지의 경우의 수만 있다. 따라서 A->B도, B->A도 경우의 수가 딱 하나 존재하고 거꾸로 B에서 A로 가는 조건을 하나하나 해주면 A가 나올 것이다.
| 기준 | A의 관점 | B의 관점 |
|---|---|---|
| 연산 1 | A * 2 | B / 2 |
| 연산 2 | A * 10 + 1 (1을 수의 오른 쪽에 추가) | (B - 1) \/ 10 (오른쪽의 1을 제거) |
이 때 A에서 B로 갈 때는 언제 어느 연산을 써야 하는지 확실치 않지만 (제가 놓친 것일 수도 있습니다. 혹여나 다른 조건이 있다면 알려주시면 감사하겠습니다!) B에서 A로 갈 때는 연산을 수행할 수 있는 조건이 확실하다.
B의 경우
- 연산 1은 무조건 B가 2의 배수일 때만 가능
- 연산 2는 무조건 B의 10의 자리가 1일 때만 가능
해당 조건에 따라 거꾸로 연산을 반복하고 특정 순간 B가 A가 되면? B->A 즉 A->B가 가능한거다.
A와 B가 딱 들어맞지 않고 중간에 연산을 할 수 없는 조건이거나 B<A의 상황이 되면 두 연산으로 도달할 수 없는 것이니까 -1을 출력하면 된다.
특정 조건에 맞으면 무조건 그 연산을 수행하면 되므로 그리디 알고리즘을 사용해보았다.
입력
A와 B를 입력받는다. $1 <= A <= B <= 10^9$까지이므로 int 범위 A와 B를 정의하고 바로 입력을 받는다.
include <iostream>
using namespace std;
int main(){
int A, B;
cin >> A >> B;
}
처리 & 출력
이후 B에서 A로 도달할 때까지 두 연산을 조건에 맞게 계속 반복해야 한다. 몇 번 반복해야 할 지 명확하지 않으므로 while 반복을 수행한다. 반복 종료 조건은 연산 중에 B가 A보다 작아지거나 연산이 실패할 경우이다.
끝 자리가 1이면서 2로 나누어지는 경우는 없으므로 로직을 간단하게 if-else로 처리한다. 연산이 실패한 경우 더 이상 반복할 필요가 없으므로 반복을 종료한다.
이후 출력 시 연산을 실제 수행했으므로 a==b 조건만 체크해주면 된다.
출력 시 경로가 있다면 연산 횟수에 +1을 하는 것을 주의하자.
정답 코드
#include <iostream>
using namespace std;
void CalcAtoB(int a, int b){
int cnt = 0;
while(a < b){
if(b % 10 == 1) { // 10의 자리가 1이면
b = (b-1)/10;
}
else if(b % 2 == 0) // 2로 나누어 떨어지면
b = b / 2;
else // 두 조건 둘 다 만족하지 않는 순간이 하나라도 있으면 A -> B 성립 X
break;
cnt++;
}
cout << (a==b ? cnt+1 : -1); // break;로 빠진 경우 a==b일 수가 없다.
}
int main(){
int A, B;
cin >> A >> B;
CalcAtoB(A, B);
}
기타
맨 처음에 그리디 방법이 먼저 생각났는데 이 문제가 이렇게 쉽게 풀린다고? 이 경우 이런 조건을 다 해결할 수 있을까? 라는 의구심에 빠져서 시도도 안 해보고 계속 고민만 하고 있었다. 우선 해보고 고민하는 습관을 들이면 실력 향상에 도움이 더 될 것 같다.
또한 문제에 대해서 여러 가지 방면 (이 문제의 경우 거꾸로 접근하는 방법)으로 조금만 생각을 비틀어서, 새로운 관점에서 보는 사고를 연습해보도록 하자.
다른 사람들은 queue나 BFS 그래프 등등을 사용하더라. 개인적으론 해당 방법으로 푸는 것이 잘 생각나진 않았지만 다른 문제를 통해 해당 알고리즘도 학습하도록 하자!