두 개의 숫자 c와 d가 주어져 있다고 가정해 보겠습니다. Amal은 처음에 두 변수 a와 b를 모두 0으로 초기화한 상태에서 시작합니다.
Amal은 여러 번의 연산을 수행하여 a를 c로, b를 d로 만들고자 합니다. 각 연산을 수행하기 전에 먼저 양의 정수 k를 하나 선택해야 하며, 이 k를 이용해 다음 세 가지 연산 중 하나를 수행할 수 있습니다.
- a와 b 양쪽 모두에 k를 더한다
- a에는 k를 더하고 b에서는 k를 뺀다
- b에는 k를 더하고 a에서는 k를 뺀다
목표는 a와 b를 각각 c와 d와 일치시키는 데 필요한 최소 연산 횟수를 구하는 것이며, 만약 불가능하다면 -1을 반환해야 합니다.
문제 접근 방식
이 문제의 핵심은 각 연산이 a와 b에 미치는 영향을 분석하는 것입니다.
- 합(a+b)의 관점: "양쪽에 k를 더하는" 연산만 합을 2k만큼 증가시키고, 나머지 두 연산은 합을 변화시키지 않습니다. 시작 값이 0이므로 a+b는 항상 짝수입니다.
- 차(a−b)의 관점: "한쪽은 더하고 다른 쪽은 빼는" 연산만 차를 ±2k만큼 변화시킵니다. 따라서 a−b 역시 항상 짝수입니다.
결국 c와 d의 홀짝성(패리티)이 서로 다르면 목표에 도달하는 것이 불가능합니다. 이는 비트 연산으로 (c ^ d)의 마지막 비트가 1인지 확인하면 간단히 판별할 수 있습니다.
풀이 단계
if ((c ^ d)가 홀수라면):
return -1
그렇지 않고 c == 0 && d == 0이라면:
return 0
그렇지 않고 c == d라면:
return 1
그 외의 경우:
return 2
위 로직을 정리하면 다음과 같습니다.
- c와 d의 패리티가 다른 경우: 어떤 연산을 조합해도 목표 값을 만들 수 없으므로 -1을 반환합니다.
- c = d = 0인 경우: 이미 목표 상태이므로 연산이 필요 없습니다(0회).
- c = d ≠ 0인 경우: k = c로 양쪽에 한 번만 더하면 되므로 1회면 충분합니다.
- 그 외의 경우(같은 패리티, 값이 다름): 첫 번째 연산으로 두 수의 차이를 맞추고, 두 번째 연산으로 합을 조정하면 되므로 항상 2회 안에 해결됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int solve(int c, int d){
if ((c ^ d) & 1)
return -1;
else if (c == 0 && d == 0)
return 0;
else if (c == d)
return 1;
else
return 2;
}
int main(){
int c = 3;
int d = 5;
cout << solve(c, d) << endl;
}
입력
c = 3, d = 5
출력
2
동작 설명
c = 3, d = 5인 경우를 살펴보겠습니다. 두 수의 패리티가 같으므로 -1은 아니고, 두 값이 서로 다르므로 정답은 2가 됩니다. 실제로 다음과 같이 두 번의 연산만으로 목표를 달성할 수 있습니다.
- k = 1을 선택하여 b에는 1을 더하고 a에서 1을 뺍니다 → (a, b) = (-1, 1)
- k = 4를 선택하여 양쪽에 4를 더합니다 → (a, b) = (3, 5)
이처럼 XOR 비트 연산과 조건 분기만 활용하면 시간 복잡도 O(1)로 문제를 해결할 수 있습니다.