[문제출처 : Codechef] N개의 동전이 있습니다. 처음에 이 모든 동전들은 똑같이 앞면이거나 똑같이 뒷면으로 놓여있습니다. 이제 플레이어가 N라운드를 진행한다고 생각해봅시다. 각 k번째 라운드에서는 1~k번째 동전을 뒤집습니다. 예를 들면, 1라운드에서는 첫번째 동전을 뒤집고, 2라운드에서는 첫번째, 두번째 동전을 뒤집습니다. 이렇게 N라운드까지 진행하면 최종적으로 앞면 또는 뒷면으로 놓여있는 동전의 개수는 몇개일까요?
이 문제도 그렇게 어렵지 않은 문제 중의 하나입니다. 하지만 잘못 생각하면 아주 비효율적으로 안좋은 방법으로 풀게 되죠. 가장 직관적인 방법은 N개의 동전을 생성한 후, 각 라운드마다 조건에 맞게 동전을 뒤집어줘서 마지막에 count하는 방법입니다. 하지만 이렇게 되면, \[\begin{aligned} \text{Memory}&=N \newline \text{Complexity}&=\sum_{i=1}^N i + N \approx O(N^2) \end{aligned} \] 굉장히 비효율적이 되겠죠? 그럼 어떻게 하면 훨씬 간단하게 해결할 수가 있을까요? 하나씩 생각해봅시다.
- 먼저 첫번째 동전은 $N$번 뒤집혀지게 됩니다.
- 두번째 동전은 $N-1$번 뒤집혀지게 됩니다.
- … 결국 마지막 동전은 1번 뒤집혀지게 됩니다.
만약 $N$이 홀수이면, [1, 3, 5, …, N]번째 동전이 처음 상태와 다를 것이고, $N$이 짝수면 [2, 4, 6, …, N]번째 동전이 처음 상태와 다를 것입니다. 조금 더 규칙을 유도해 낸다면, 처음과 같은 상태의 동전은, $\lfloor \frac{N}{2}\rfloor$개만큼 있을 것이고, 처음과 다른 상태의 동전은 $\lfloor\frac{N+1}{2}\rfloor$개만큼 있을 것입니다. 그럼 이 간단한 풀이법을 코딩으로 마무리 하겠습니다.
def guessNumFlipped(i, q, N):
# i는 초기 동전의 상태 (1은 앞면, 2는 뒷면)
# q는 알고싶은 동전의 상태 (1은 앞면, 2는 뒷면)
if i == q:
return N/2
else:
return (N+1)/2
>>> print guessNumFlipped(1, 1, 5)
2
>>> print guessNumFlipped(1, 2, 5)
3이렇게 하면 메모리도 전혀 사용하지 않고, complexity도 $O(1)$으로 말도 안되게 효율적으로 풀 수 있겠죠?