[Python] 34019번 [G] Grounded Number

https://www.acmicpc.net/problem/34019

---

 

25/06/05

 

 

찍어서 맞추기는 쉽지만 증명하기 어려운 애드 혹 문제다.

---

 

문제 접근 방식:

 

 

그냥 작은 케이스에 대해 나열 해보면, 짝수일때는 가능하고 홀수일때는 불가능하다는 걸 확인할 수 있다.

 

실제로 그렇게 제출하면 맞을 수 있는데, 이를 증명하는 건 쉽지 않다.

 

증명 과정은 다음과 같다.

 

$i$번째 연산 과정 전의 수를 $n_i$라고 하자. $n_i - i = d_i$라고 정의하자.

 

만약 $n_i$에서 연산을 한 결과가 $+1$인 경우, 즉, $n_i$가 $i$의 배수인 경우, 다시 말해, $i$가 $n_i$를 나눌 때, 같은 이야기로, $i$가 $d_i + i$를 나눌때, 즉, $i$가 $d_i$를 나눌 때, $d_{i+1} = n_{i+1} - (i+1) = n_i + 1 - i - 1 = d_i$가 된다.

 

그러지 않은 경우, $d_{i+1} = n_{i+1} - (i+1) = d_i - 2$가 된다.

 

따라서, $i$가 어떻게 되든 간에, $d_i$의 홀짝성은 변하지 않는다.

 

$n_1$이 홀수인 경우, 즉, 처음 주어진 $N$이 홀수인 경우, $d_1 = n_1 - 1$이므로 $d_1$은 짝수가 된다.

 

$i$는 연산을 할 때마다 $1$씩 증가하는 변수이므로, $i$가 $d_i$를 나누지 않는 경우는 무조건 생긴다. 연산을 할 때마다 $d_i$는 감소하거나 그대로인 반면 $i$는 계속 증가하기 때문이다.

 

$d_i$가 감소할 때($i$가 $d_i$를 나누지 않을 때) $2$씩 감소하므로, $d_i = 0$인 부분이 존재할 수 밖에 없다.

 

$d_i = 0$은 $n_i = i$인 부분이 된다. 즉, 이 이후에는 $n_i$도 $1$씩, $i$도 $1$씩 증가하므로 발산한다.

 

$n_1$이 짝수인 경우, 즉, 처음 주어진 $N$이 짝수인 경우, $d_1$은 홀수가 된다.

 

마찬가지 논리로, $d_i$가 계속 감소하다보면 $d_i$가 $-1$이 되는 부분이 존재할 수 밖에 없다.

 

즉, 이 부분은 $i > n_i$가 되는 부분이고, 이 부분 이후에는 $i$는 계속 증가하면서 $n_i$를 나누지 않게 되므로 $0$으로 수렴한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 34019번 [G] Grounded Number
# 불변량 찾기
'''
접근 방법:
1 -> 2 -> 3 -> ...
2 -> 3 -> 2 -> 1 -> 0
3 -> 4 -> 5 -> 4 -> 5 -> ...
4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
5 -> 6 -> 7 -> 6 -> 5 -> 6 -> ...
6 -> 7 -> 6 -> 7 -> 6 -> 5 -> 4 -> ... -> 0
7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7 -> ...
보니까 홀수일 때에는 발산하는 것 같다.
WHY?
Prove)
d_i = n_i - i라고 하자.
만약 n_i에서 연산을 한 결과가 +1인 경우 = n_i가 i의 배수일 때 = i가 n_i를 나눌 때 = i가 d_i + i를 나눌 때 = i가 d_i를 나눌 때
d_{i+1} = n_{i+1} - (i+1) = n_i + 1 - i - 1 = d_i
만약 n_i에서 연산을 한 결과가 -1인 경우 = i가 n_i를 나누지 않을 때 = i가 d_i를 나누지 않을 때
d_{i+1} = n_{i+1} - (i+1) = n_i - 1 - i - 1 = d_i - 2
따라서, d_i는 연산을 거듭해도 그 홀짝성이 바뀌지 않는다.

n_1이 홀수인 경우, 즉, 처음 주어진 N이 홀수인 경우 n_1 - 1 = d_1 = 짝수가 된다.
i는 계속 증가하므로, i가 d_i를 나누지 않을 때는 존재할 수 밖에 없다.
그게 반복된다면 결국 d_i가 줄어들어 d_i = 0이 될 것이다.
즉, 그때는 n_i = i인 경우가 된다.
이 이후에는 n_{i+1} = n_i + 1이 되고, i도 1 증가하므로, 1 증가 과정이 반복해서 이뤄진다.
따라서 무한으로 증가한다.

n_1이 짝수인 경우, 즉, 처음 주어진 N이 짝수인 경우 n_1 - 1 = d_1 = 홀수가 된다.
i는 계속 증가하므로, i가 d_i를 나누지 않는 경우는 존재할 수 밖에 없다.
그게 반복된다면 결국 d_i가 줄어들다가 d_i가 음수가 될 것이다.
즉, i > n_i가 되는 순간이 온다.
이 이후에는 계속 i가 n_i를 나누지 않으므로, -1만 계속 되다가 0으로 수렴한다.
'''
print('No' if int(input()) % 2 else 'Yes')