알고스팟 - 어린이날 (CHILDRENDAY) 문제 설명

알고스팟의 어린이날 문제에 대해 설명해보겠습니다.

문제 : https://algospot.com/judge/problem/read/CHILDRENDAY

먼저, 어린이날 문제를 요약해보도록 하겠습니다. 모든 어린이들의 총합은 N 명이고, 우리는 N 명의 어린이들에게 균등한 개수의 선물을 나눠줘야 합니다. 예를 들어, 각 어린이들에게 한 개의 선물을 나눠준다고 하면, N개의 선물이 필요하게 됩니다. 단, M명의 욕심쟁이 어린이들에게는 한 개의 선물을 더 주어야 하기 때문에 최소한으로 주어야 하는 선물의 총 합은 N+M이 됩니다.

• N명의 어린이들에게 균등한 수의 선물을 나눠줘야 한다.
• N명 중 M 명의 욕심쟁이 어린이들에게 선물 하나를 더 줘야 한다.
• 선물 개수 총합은 주어진 숫자 목록의 숫자들만 사용해야 한다.

주어진 숫자들만을 이용해서 어린이들에게 나눠줄 선물의 총합을 y라고 하겠습니다. 그러면, 일반 어린이와 욕심쟁이 어린이들에게 규칙에 따라 선물을 나누어 주고 남는 선물이 존재하지 않아야 합니다. 이를 수학적으로 표현하면 (y-m) mod n =0가 됩니다. 문제를 조금 더 쉽게 하기 위해 M을 0으로 가정하면, y mod N = 0이 됩니다. 이 말은 N명의 어린이들에게 y개의 선물을 균등하게 나눠주었을 때 남는 것이 없다는 것을 의미합니다.

예를 들어, 위와 같이 어린이 수 N =4이고, 선물의 개수 y = 12라면, y mod N = 12 mod 4 = 0, 즉, 각 어린이들에게 3개의 선물을 나눠주면 남는 것이 없어지게 됩니다.

우리는 N명의 일반 어린이들에게 균등한 개수의 선물을 나누어 주고, 그 중에서 M 명의 욕심쟁이 어린이들에게는 한 개의 선물을 더 주어야 합니다. 이를 수학적으로 표기하기 위해, 우리는 N명의 어린이들에게 나누어주는 선물의 개수를 p라고 가정하겠습니다. 그러면, N 곱하기 p는 y를 만족합니다. 즉, N 명의 어린이들에게 각각 p개의 선물을 나눠주면 총 y개가 된다는 의미입니다. 만약, M이 0이 아니라면, N명의 어린이들에게 p개의 선물을 나누어 주고 나서 남은 선물의 개수는 M이 되어야 M명의 욕심쟁이 어린이들에게 한 개의 선물을 더 줄 수 있게 됩니다. 따라서, y는 N * p + M을 만족합니다. 

위와 같이 N=4, M=1 그리고 p=3 어린이4가 욕심쟁이 어린이라고 가정하면, 위의 식에 따라, 4*3+1=13=y가 됩니다.

앞서 정의한 식 N * p + M = y는 y개의 선물을 N명에게 각각 p개씩 나누어 주면 M개가 남는다는 것을 의미합니다. 이 말을 다시 쓰면, y 를 N으로 나눈 나머지는 M이 된다는 의미가 됩니다. 위의 그림의 예시와 같이, 어린이가 네 명이고, 그 중에서 욕심쟁이 어린이가 한명, 총 선물의 개수가 13개라고 하면, 네명의 어린이들에게 3개씩 선물을 주고 남는 선물 한 개는 욕심쟁이 어린이가 가지게 되어 모든 선물을 사용하게 됩니다.

예를 들어, N=4, M=1 그리고 y=13이면 위의 그림과 같이 나타낼 수 있습니다.

우리는 앞서 설명한 조건들을 만족하는 y를 찾아야 합니다. 그리고 y를 만들기 위해서 문제에서 제시한 숫자들 만을 사용해야 합니다. 따라서, 우리가 만들 수 있는 y 값에 대해 알아보겠습니다. 주어질 숫자들은 0부터 9까지의 숫자 중 임의로 주어집니다. 주어진 숫자의 개수를 k라고 할 때, 우리는 각 숫자들을 a1,a2 이런 식으로 표기하겠습니다. 그러면, 우리가 주어진 숫자를 이용해서 만들 수 있는 조합은 아래 그림과 같습니다. a_i라는 숫자가 있으면, 해당 숫자에 10을 곱해서 십의 자리로 만든 후에 일에 자리에는 새로운 숫자를 삽입합니다. 오른쪽에는 숫자 1,2,3이 주어졌을 때, 각 자리수 크기에 따른 모든 조합을 나타내고 있습니다. 이런식으로 주어진 숫자들을 통해 무한히 많은 숫자들의 조합을 찾을 수 있으며, 우리는 이 중에서 y mod N = 0을 만족하는 가장 작은 y 값을 찾아야 합니다.

숫자가 1,2,3으로 주어졌다고 하자. 한 자리 숫자는 1,2,3이 가능하다. 두 자리 숫자는 11, 12, 13, 21, 22, 23, 31, 32, 33이 가능하다. 세 자리 숫자는 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332 ,333이 가능하다.

단순 무식한 방법

y값을 찾기 위한 가장 단순 무식한 방법은 조합 가능한 모든 숫자들을 작은 값부터 하나씩 검사하는 방법입니다. 예를 들어, 주어진 숫자가 1,2,3일 경우, 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33 순으로 처리해야 합니다. 이러한 방식으로 처리하기 위해 현재 처리할 숫자에 대해 이후의 자식 값들을 자료구조 큐에 삽입해주어야 합니다.

먼저, 처음에는 0이라는 값을 사용합니다. 0 이후의 조합할 수 있는 숫자는 1,2,3이 되고, 이를 순서대로 큐에 삽입합니다.

그리고 더 이상 추가할 값이 없으므로, 큐의 가장 앞에 있는 숫자 1을 추출합니다. 그리고 1로 조합할 수 있는 값인 11, 12, 13을 순서대로 큐에 삽입합니다.

다음으로, 큐에서 2를 추출하여 조합 가능한 값인 21, 22, 23을 순서대로 큐에 삽입합니다.

다음으로, 큐에서 3를 추출하여 조합 가능한 값인 31, 32, 33을 순서대로 큐에 삽입합니다. 이런 식으로 큐를 사용하여 현재 처리할 값의 조합 가능한 값들을 큐에 삽입함으로써 모든 조합 가능한 숫자들을 가장 작은 값부터 처리할 수 있습니다.

N = 7이고 사용 가능 숫자가 1,2,3일 때, 모든 어린이 들에게 선물을 나누어 주기 위해 선물의 개수는 최소 N개 이상이 여야 한다. 1 < 7 이므로 통과 2 < 7 이므로 통과 3 < 7 이므로 통과 11 mod 7 = 4 12 mod 7 = 5 13 mod 7 = 6 21 mod 7 = 0 ## 21은 7로 나누어 떨어지기 때문에 7명의 학생들에게 균등한 개수의 선물을 나누어 주고 남는 것이 없게 된다. 그러므로 답이 된다.

앞서 설명한 방법을 통해 큐에 순서대로 저장된 처리할 값들을 추출하여 해당 값을 N으로 나눈 나머지가 0이 되는지 확인해야 합니다. 먼저 이 방법이 제대로 작동하는지 예시를 들어보겠습니다. N=7이고, 사용가능한 숫자가 1,2,3이라고 하겠습니다. 이때, 모든 어린이들에게 균등하게 선물을 나누어 주기 위해 선물의 개수는 최소 N개 이상이여야 합니다. 따라서, 처음 추출되는 1, 2, 3은 7보다 작기 때문에 검사를 하지 않고 통과합니다. 그 이후로 11, 12, 13은 7로 나눈 나머지가 0이 아니기 때문에 어린이들에게 선물을 균등하게 나누어 주고 남는 선물이 존재하게 되므로 정답이 아닙니다. 21은 7로 나눈 나머지가 0이기 때문에 정답이 됩니다.

단순 무식한 방법의 문제점1

이러한 단순 무식한 방법으로 답을 얻어낼 수 있습니다. 그러나, 이 방법의 문제점이 존재하는데요, 임의로 조합된 두 숫자 a_i와 a_j가 존재할 때, a_i mod N = a_j mod N 인 경우에는 a_i를 사용하여 이후의 조합될 숫자들과 a_j이후의 조합될 숫자들의 결과는 항상 동일함에도 불구하고 각각 큐에 넣고 처리를 하게됩니다. 예를 들어, 사용 가능 숫자가 3, 4, 5 이고 N =7이며 33과 54를 처리할 경우, 33 mod 7 =5가 되고, 54 mod =7이 되어 동일한 나머지 값을 가집니다. 이때, 33의 조합 가능한 숫자는 333, 334, 335가 되는데요, 각각 7로 나눈 나머지는 4, 5, 6이 됩니다. 마찬가지로, 54의 조합가능한 숫자는 543, 544, 545가 되는데요, 각각의 7로 나눈 나머지 값은 4, 5, 6이 됩니다. 이후에도 항상 동일한 결과가 나오게 되는데요, 이러한 중복 계산을 방지하기 위해, 더 작은 값인 33의 자식들을 큐에  넣었다면, 54와 같이 나머지가 값이 같은 값은 자식들을 큐에 넣지 않도록 해야 합니다.

단순 무식한 방법의 문제점2

단순 무식한 방법의 또 다른 문제점은 사용 가능한 숫자를 통해 조합을 하다보면 그 값이 32비트 정수형의 범위를 쉽게 넘게됩니다. 예를 들어, 사용 가능 숫자가 1이라면, 한번 검사를 할 때마다 10배씩 증가하게 되어 10번만 검사해도 처리할 값이 10억을 넘게됩니다. 사칙 연산과 다르게 mod 연산은 몇 번을 해도 항상 동일한 값을 반환합니다. 

(x*100 + x*10 + x) mod N = ((((x mod N) * 10 + x) mod N ) * 10 + x) mod N (x*10 + x) mod N = ((x mod N) * 10 + x) mod N

예를 들어, 111을 7로 나눈 나머지는 6이됩니다. 또한, 1을 7로 나눈 나머지에 10을 곱하고 1을 더한 후에 다시 7로 나눈 나머지를 다시 10을 곱하고 1을 더한 후에 다시 7로 나눈 나머지는 동일하다는 것을 알 수 있습니다. 따라서, 우리는 항상 전체 값을 보관하는 대신, 나머지 값을 보관함으로써 크기를 항상 N보다 작게 유지하면서 동일한 결과를 얻을 수 있습니다.

문제 해결 방법1

앞서 설명한 첫 번째 문제를 해결하기 위해 이미 사용된 나머지 값들을 표시하는 배열 used를 생성합니다. used 배열은 N의 크기만큼 필요하며, 큐를 통해 y를 작은 값부터 하나씩 검사를 할 때, y mod N을 used의 인덱스로 하여 조회를 했을 때, 초기값인 0일 경우, 아직 해당 나머지 값이 한 번도 존재하지 않았다는 의미가 되기 때문에 used를 1로 변경하고 해당 값을 큐에 삽입합니다. 만약 used가 0이 아니라면, 해당 나머지는 이미 큐에 넣어졌다는 의미이므로 해당 값은 큐에 넣지 않고 버립니다. 

다음과 같이 N=7이고 사용 가능한 숫자가 1일 경우, 1부터 11, 111, 1111로 증가하여 각 값들에 대해 나머지를 검사하여 이미 사용된 나머지는 버림으로써 중복 계산을 방지할 수 있습니다.

처음 숫자 y=1 에 대하여 y mod N = 1 mod 7 = 1이며, used[1]=0이므로 used[1]=1로 저장하고 1을 큐에 넣는다.

큐에서 추출한 숫자 1로 조합한 y=11에 대하여, 11 mod 7 = 4이며 used[4]=0이므로 used[4]=1로 저장하고 11을 큐에 넣는다.

큐에서 추출한 숫자 11로 조합한 y=111에 대하여, 111 mod 7=6이며 used[6]=0이므로 used[6]=1로 저장하고 111을 큐에 넣는다.

큐에서 추출한 숫자 111로 조합한 y=1111에 대하여, 1111 mod 7=5이며 used[5]=0이므로 used[5]=1로 저장하고 1111을 큐에 넣는다.

큐에서 추출한 숫자 1111로 조합한 y=11111에 대하여, 11111 mod 7 = 2이며 used[2]=0이므로 used[2]=1로 저장하고 11111을 큐에 넣는다.

큐에서 추출한 숫자 11111로 조합한 y=111111에 대하여 111111 mod 7 = 0이며, 이는 111111개의 선물이 N명의 어린이들에게 균등한 개수의 선물을 나누어 줄 수 있다는 것을 의미한다. 따라서 111111을 결과로 출력한다.

문제 해결 방법2

두번째 문제를 해결하기 위해 우리는 y의 전체 값을 큐에 넣지 말고, y mod N 값만 넣어서 사용하면 y의 크기 제한이 없어지게 됩니다. 그러나, y가 아닌 y mod N을 큐에 넣으면 y mod N =0인 y를 발견하더라도 해당 y의 전체 값을 알 수 없게 됩니다. 예를 들어, N=7, M =0이고 사용 가능 숫자가 1일 때, 큐에 y mod N 값을 넣는다면 1, 4, 6, 5, 2을 넣고 마지막 2 조합 값인 21을 7 로 나누면 0이 되지만, 답은 21이 아니라 111111이 됩니다. y의 전체 값을 알아내기 위해, 나머지 값을 인덱스로 하여 매번 선택한 숫자를 배열에 저장해야 합니다. 또한, 직전의 선택한 숫자를 알기 위해서는 직전의 나머지 값도 새로운 배열에 저장해야 합니다.

이를 위해, 부모의 위치를 보관할 배열과 현재 선택한 숫자를 보관할 배열을 사용하면 됩니다.

 

큐에서 추출한 값을 통해 조합한 숫자를 mod N 으로 한 값을 인덱스로 했을 때, parent의 값이 -1이라면 해당 나머지 값이 한번도 사용되지 않았으므로 해당 parent에는 큐에서 추출한 값을, choice에는 방금 선택한 숫자를 입력합니다. parent와 choice에서 0부터 N-1까지의 인덱스는 조합한 값이 N보다 작을 경우의 나머지를 인덱스로 하여 저장하는 공간이고, N부터 2N-1까지는 조합한 값이 N이상일 경우의 나머지를 인덱스로 하는 저장공간입니다.

예를 들어, N=7, M=0 그리고 사용 가능 숫자가 1일 경우는 다음과 같이 나타낼 수 있습니다.

 

처음 큐에서 0을 추출하고 0의 조합 가능 숫자 1<N이고, parent[1]=-1이므로 parent[1]=0으로 변경하고 choice[1]=1로 저장합니다. 그리고 1을 큐에 넣습니다.

큐에서 1을 추출하고 1의 조합 가능 숫자 11>N이므로 11 mod 7 = 4에 N을 더한 11을 인덱스로 하여 parent[11]=-1이므로 parent[11]=1으로 변경하고 choice[4]=1로 저장합니다. 그리고 4를 큐에 넣습니다.

큐에서 4를 추출하고 4의 조합 가능 숫자 41>N이므로 41 mod 7 = 6에 N을 더한 13을 인덱스로하여 parent[13]=-1이므로 parent[13]=11로 변경하고 choice[13]=1로 저장합니다.. 그리고 6을 큐에 넣습니다.

큐에서 6을 추출하고 6의 조합 가능 숫자 61>N이므로 61 mod 7 = 5에 N을 더한 12을 인덱스로 하여 parent[12]=-1이므로 parent[12]=13으로 변경하고 choice[12]=1로 저장하고 5를 큐에 넣습니다.

큐에서 5를 추출하고 5의 조합 가능 숫자 51>N이므로 51 mod 7 = 2에 N을 더한 9을 인덱스로하여 parent[9]=-1이므로 parent[9]=12로 변경하고 choice[9]=1로 저장하고 2을 큐에 넣습니다.

큐에서 2을 추출하고 2의 조합 가능 숫자 21>N이므로 21 mod 7 = 0에 N을 더한 7을 인덱스로 하여 parent[7]=-1이므로 parent[7]=9으로 변경하고 choice[7]=1로 저장합니다.

나머지가 0이므로 더 이상 탐색할 필요가 없게 되었으므로, 인덱스 N=7부터 parent가 가리키는 부모 인덱스의 위치를 추적하면서 choice의 숫자들을 앞에 추가해줍니다.

결과적으로 111111이라는 값을 도출하게 됩니다.

-----------------------------------------------------------------------------------