문제 개요
하나의 숫자 n이 주어집니다. 게임이 시작될 때 n의 초기값은 v이며, 플레이어는 다음 연산을 0회 이상 자유롭게 반복할 수 있습니다.
- n보다 작은 양의 정수 x를 선택합니다. 단, x는 n의 약수가 아니어야 합니다.
- 선택한 x를 n에서 뺍니다.
플레이어의 목표는 이 연산을 적절히 활용해 최종적으로 n의 값을 최소한으로 만드는 것입니다.
예를 들어 입력이 n = 8이라면 출력은 1이 됩니다. 첫 번째 턴에 x = 3을 선택하면 n은 5가 되고, 두 번째 턴에 x = 4를 선택하면 n = 1을 얻을 수 있기 때문입니다.
접근 방법
언뜻 복잡해 보이지만, 이 문제의 답은 아주 간단한 규칙 하나로 결정됩니다. 경우를 나누어 살펴보겠습니다.
- n = 1인 경우: n보다 작은 양의 정수가 존재하지 않으므로 어떤 연산도 수행할 수 없습니다. 따라서 답은 1입니다.
- n = 2인 경우: 선택 가능한 x는 1뿐이지만, 1은 2의 약수이므로 사용할 수 없습니다. 어떤 연산도 불가능하므로 답은 2입니다.
- n이 3 이상의 홀수인 경우: x = 2를 선택할 수 있습니다. 홀수는 2로 나누어떨어지지 않으므로 2는 n의 약수가 아니기 때문입니다. 이후에도 계속 2를 빼면 결국 1에 도달합니다.
- n이 4 이상의 짝수인 경우: x = n − 1을 선택하면 한 번의 연산만으로 1을 만들 수 있습니다. n − 1은 홀수이므로 짝수인 n의 약수가 될 수 없습니다.
결국 n = 2일 때만 답이 2이고, 그 외의 모든 경우에는 답이 1이 됩니다.
알고리즘 단계
위 분석을 바탕으로 해결 절차는 다음과 같습니다.
if n == 2 then:
return 2
return 1
C++ 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(int n){
if (n == 2){
return 2;
}
return 1;
}
int main(){
int n = 8;
cout << solve(n) << endl;
}
입력
8
출력
1
마무리
이 문제는 조건을 꼼꼼히 분석하면 O(1) 시간 복잡도로 해결할 수 있는 매우 효율적인 문제입니다. 핵심은 '약수가 아닌 수를 뺄 수 있다'는 규칙 덕분에 대부분의 경우 1까지 도달할 수 있다는 점, 그리고 유일하게 n = 2일 때만 어떤 연산도 수행할 수 없다는 점을 파악하는 것입니다.