[문제 출처 : Codechef] K개의 핵 반응로가 있습니다.(0에서 K-1까지의 index를 갖습니다.)
입자들은 0번 반응로로 쏘아집니다. 그렇게 0번 반응로는 N개의 입자까지 모으다가 N+1번째 입자가 쏘아짐과 동시에 1번 반응로로 입자를 이동시키고 자신이 가지고 있던 입자들을 다 파괴시켜버립니다. 마찬가지로 1~K-2번 반응로도 각각 N개까지 모으다가 N+1번째 입자가 들어옴과 동시에 자신+1번째 반응로로 입자를 하나 전달하고 자신이 가지고 있던 모든 입자를 파괴합니다. K-1번째(마지막) 반응로는 전달할 반응로가 없기 때문에 그냥 N+1번째 입자가 들어오면 모두 파괴시킵니다.
A개의 입자를 쏠 때, K개의 반응로와 각 반응로가 N개의 입자까지 수용할 수 있다고 가정했을 때, 최종적인 반응로들의 입자 분포는 어떻게 될까요?
가장 간단하게 생각해 볼 수 있는 것은 입자를 하나씩 쏴보고 반응로의 상태에 따라서 옮기고, 파괴하는 것일 것입니다. 하지만 사탕 나눠주기 문제에서도 언급했듯이, 조금만 생각하면 훨씬 더 빠르고 효율적인 코드를 짤 수 있습니다. 조금 자세히 들여다보면, 이 문제는 N진수의 K자리 카운터로 A를 카운트하는 문제와 같다는 것을 아실 수 있으실 것입니다 :) 우리가 늘상 쓰는 10진수 카운터를 보시면, 0에서 출발해 9까지 센 다음 마지막 10이 되었을 때는 10의 자리에 1을 넘겨주고 자신은 0이 됩니다. 이제 감이 오시죠?
이렇게 생각만으로 문제를 다 풀었습니다. 이제 간단하게 코드로 구현해 보고, 결과를 확인해 봅시다 :)
def reactorStatus(A, N, K):
status = []
#0번 반응로가 가장 작은 단위의 자릿수가 됩니다.
for i in range(K):
status.append(A % (N+1))
A /= (N+1)
return status
>>> print reactorStatus(3, 1, 3)
[1, 1, 0]정답을 보면 정말정말 쉬운 문제지만, 또 자칫 잘못하면 비효율적인 코드가 나올 수 있으니 주의하세요 :)