도전! 정보올림피아드

369 게임

이번 글에서는 올해 5월 23일, 전국 17개 시도에서 열렸던 지역본선 대회의 중등부 3번 ‘369 게임’ 문제를 소개하고 풀이방법에 대해 알아본다. 친구들과 놀 때 많이 하던 369 게임이 문제로 나왔는데, 주어진 수의 범위(10100,000)가 굉장히 커서(무려 10만 자리의 수다, 10만까지가 아니다) 시간초과가 나기 쉬운 문제다.

369 게임여러 사람이 둘러 앉아 즐기는 369 게임은 다음과 같은 규칙을 가지고 있다.● 규칙: 양의 정수 A에서 시작하여 차례로 사람들이 돌아가면서 숫자를 하나씩
증가하면서 불러 나간다. 단, 부르는 숫자가 3의 배수이거나 그 숫자에 3, 6, 9중
하나라도 들어 있는 경우에 숫자는 부르지 않고 박수를 친다.● 규칙: 예를 들어, 369 게임을 17부터 시작하는 경우를 생각해보자. 박수를 X로 표현하면,
이 게임의 진행은 17-X-X-20-X-22-X-X-25-X-X-28-X-X …과 같을 것이다.시작하는 양의 정수 A와 끝나는 양의 정수 B가 주어졌을 때, 박수를 치는
총 횟수를 구하는 프로그램을 작성하시오.
소스 파일의 이름은 game369.c 또는 game369.cpp이며 수행시간은 1초를 넘을 수 없다.
사용하는 메모리는 128MB를 넘을 수 없다.[입력 형식]
다음 정보가 표준 입력으로 주어진다. 한 줄에 시작하는 양의 정수 A와 끝나는 양의 정수 B가 순서대로 주어진다.
두 수의 범위는 1 ≤ A ≤ B ≤ 10100,000이다. 단, 좁은 범위 1≤ A ≤ B ≤ 106인 경우의 입력에
대해서만 올바른 답을 출력해도 점수의 30%를 받을 수 있다.
[출력 형식]
다음 정보를 표준 출력으로 출력한다. 박수치는 총 횟수를 20,150,523으로 나눈 나머지를 출력한다.[입력과 출력의 예]
입력(1)
1 12
출력(1)
4입력(2)
29 39
출력(2)
11입력(3)
12345 123456789
출력(3)
17517670(출처: 2015년 정보올림피아드 지역본선 중등부 3번)

30점 풀이

우선 쉽게 생각할 수 있는 방법으로 반복문을 이용해 모든 경우를 다 검사하는 방법이 있다. chk(p) 함수를 p가 3의 배수이거나 3,6,9가 들어간 수이면 true를 return하는 함수로 정의한다. 그런 다음에 a부터 b까지 모든 수에 대해서 chk() 함수를 호출해 true이면 s를 1씩 증가시키는 방법으로 답을 구할 수 있다. chk() 함수는 먼저 p가 3의 배수 (p%3==0) 이면 true를 return 한다. 만약 3의 배수가 아니라면 끝자리부터 하나씩 숫자를 검사해 3,6,9인 경우 true를 return한다. 두 경우가 모두 아니라면 false를 return 한다. 여기서 p%10은 수의 가장 마지막 자리 숫자가 되며, p/=10은 마지막 자리 숫자를 제외하고 남은 수다.

이 방법은 O(n) 알고리즘으로 106까지의 입력에 대해서는 제한시간(1초) 내에 해결이 가능하지만 10100,000까지는 해결할 수 없다. 좀 더 빠르게 답을 찾는 방법이 필요하다.

<리스트 1> 모든 경우를 다 조사하는 방법 (30점 풀이)#include < iostream>
#define R 20150523
using namespace std;int s,a,b;
bool chk(int p) {
int t;
if(p%3==0) return true;
while(p>0) {
t = p%10;
if (t==3 || t==6 || t==9) return true;
p /= 10;
}
return false;
}int main() {
int i;
cin >> a >> b;
for(i=a; i < =b; i++) {
if(chk(i)) s = (s+1)%R;
}
cout < < s;
return 0;
}

[단계 1] i 자리까지 3,6,9가 포함된 수

어떤 수 p가 주어졌을 때, 1부터 p까지 3의 배수이거나 3,6,9가 들어간 수의 개수를 구하는 방법은 다음과 같이 크게 3가지로 나누어 볼 수 있다.

1. n(3의 배수) + n(3의 배수가 아니면서 3,6,9가 들어간 수)
2. n(3,6,9가 들어간 수) + n(3,6,9가 들어있지 않은 3의 배수)
3. n(3의 배수) + n(3,6,9가 들어간 수) - n(3의 배수이고 3,6,9가 들어간 수)

여기에서는 두 번째 방법을 사용해 먼저 3,6,9가 들어간 수의 개수부터 구해보자. i 자리까지의 수 중에서 3,6,9가 한 개라도 있는 수의 집합을 Ai라 하고, 3,6,9가 한 번도 나오지 않은 수의 집합을 Bi로 놓자. B1은 {0,1,2,4,5,7,8}이 있어 n(B1) = 7이 되고, n(B2)는 n(B1) * 7이므로 49가 된다. 이를 일반화하면 n(Bi) = n(Bi-1) * 7이 된다. 한편, A1은 {3,6,9}이고 n(A1) = 3이 된다. A2는 A1 뒤에 숫자가 붙는 경우와 B1뒤에 숫자가 붙는 경우로 나눠서 계산할 수 있다. A1 뒤에 오는 숫자는 0부터 9까지 모두 다 올 수 있으므로 n(A1) * 10 = 30이 된다. B1 뒤에 오는 숫자는 {3,6,9} 중 하나가 와야 하므로 n(B1) * 3 = 21이 된다. 따라서, n(A2)는 30 + 21 = 51이 되고, 이를 일반화하면 n(Ai) = n(Ai-1) * 10 + n(Bi-1) * 3으로 표현할 수 있다. <표 1>은 4자리까지 각각의 경우의 수를 나타낸 것이다.



지금까지의 수식을 프로그램으로 만들면 <리스트 2>가 된다. 경우의 수가 커질 수 있으므로 문제에 주어진 대로 R(=20150523)로 나눈 나머지를 저장한다.

<리스트 2> A, B 배열의 값 구하기B[0] = 1;
for(i=1; i< =len; i++) {
A[i] = (A[i-1]*10 + B[i-1]*3) % R;
B[i] = (B[i-1]*7) % R;
}

[단계 2] i 자리까지 3,6,9가 포함되지 않은 3의 배수

i 자리까지 3,6,9가 포함되지 않은 수를 3으로 나눈 나머지가 0인 집합을 Ci, 나머지가 1인 집합을 Di, 나머지가 2인 집합을 Ei라 놓자. C1 = {0} 하나만 있으므로 n(C1) = 1이 되고, D1 = {1,4,7}과 같이 세 개가 있으므로 n(D1) = 3, 마찬가지로 E1 = {2,5,8}로 n(E1) = 3이 된다. C2가 되는 방법은 세 경우로 나누어 지는데, C1과 C1이 결합한 경우(00), D1과 E1이 결합한 경우 (12,15,18,42,45,48,72,75,78), E1과 D1이 결합한 경우(21,24,27,51,54,57,81,84,87)로 총 19개가 있다. 개수를 수식으로 표현하면 n(C2) = n(C1)*n(C1) + n(D1)*n(E1) + n(E1)*n(D1) = 1*1+3*3+3*3=19가 되고, 이를 일반화하면 n(Ci) = n(Ci-1)*n(C1) + n(Di-1)*n(E1) + n(Ei-1)*n(D1)가 되는데, n(C1)=1, n(D1)=3, n(E1)=3이므로, n(Ci) = n(Ci-1)*1 + n(Di-1)*3 + n(Ei-1)*3이 된다.

같은 원리로 n(Di) = n(Ci-1)*n(D1) + n(D i-1)*n(C1) + n(E i-1)*n(E1) = n(Ci-1)*3 + n(D i-1)*1 + n(Ei-1)*3이 되고, n(Ei) = n(Ci-1)*n(E1) + n(D i-1)*n(D1) + n(E i-1)*n(C1) = n(Ci-1)*3 + n(D i-1)*3 + n(Ei-1)*1이 된다. 여기까지 나온 식을 이용해 값을 계산해보면 <표 2>와 같다.



<표 2>를 보면 n(Di)와 n(Ei)의 값이 계속해서 같음을 알 수 있다. 이를 이용하면 n(Ei)를 따로 구할 필요가 없으며, 앞에서 정리한 식은 아래와 같이 더 간단히 만들 수 있다.

n(Ci) = n(Ci-1)*1 + n(Di-1)*6
n(Di) = n(Ci-1)*3 + n(D i-1)*4



이것을 프로그램으로 구현하면 <리스트 3>과 같이 된다.

<리스트 3> C, D 배열의 값 구하기 C[0] = 1;
for(i=1; i< =len; i++) {
C[i] = (C[i-1]*1 + D[i-1]*6) % R;
D[i] = (C[i-1]*3 + D[i-1]*4) % R;
}

[단계 3] 1~p까지 박수 횟수 구하기

이제 앞에서 구한 A~D 배열을 이용하여 1~p까지 박수를 친 횟수를 구해보자. 12345로 예를 들면, 12345까지의 수는 시작하는 숫자에 따라 다음과 같이 구분해 볼 수 있다. 다음에서 x는 0~9까지 모든 숫자를 의미한다.

0xxxx, 10xxx, 11xxx, 120xx, 121xx, 122xx, 123xx, …

123xx에서 처음으로 3이 나왔으므로 이후의 모든 수는 박수를 치게 된다. 따라서 12345-12300+1=46을 먼저 구할 수 있다.

0xxxx는 0으로 시작하는 4자리 수를 의미한다. 4자리 수까지 3,6,9가 들어가는 개수는 n(A4) 이므로 7599를 답에 추가한다. 또한 지금까지 나온 자릿수의 합이 0이므로 다음 4자리 숫자의 합이 C그룹이면 3의 배수가 된다. 이것은 n(C4)를 의미하는데, 한가지 주의할 점은 00000과 같이 모두 0인 경우는 0이 되므로 이것은 포함하지 않아야 한다. 따라서 811-1=810을 답에 추가한다.

같은 방법으로 10xxx는 10으로 시작하는 3자리 수이므로, 3자리 수까지 3,6,9가 들어가는 수의 개수, n(A3)=657을 더한다. 그리고 10까지 자릿수의 합은 1이므로 나머지 3자리 숫자의 합이 E그룹이면 3의 배수가 된다. 따라서, n(E3) = n(D3) = 117을 답에 추가한다. 11xxx도 같은 방법으로 n(A3)=657과 n(D3) = 117을 답에 추가한다. 이런 식으로 120xx, 121xx, 122xx도 해당하는 A, C, D 배열의 값을 참조하여 답에 추가하면 12345까지 친 박수의 횟수가 9066 + 1093 + 46 = 10205번이라는 것을 알 수 있다.

[최종 단계] a~b까지 박수 횟수 구하기

[단계 3]까지 만들었으면 [최종 단계]는 쉽다. a~b까지의 횟수는 1~b까지의 횟수에서 1~(a-1)까지의 횟수를 빼면 된다. 여기서 주의할 점은 R(=20150523)으로 나눈 나머지를 구하다 보니 n(b)가 n(a-1)보다 작은 값이 나올 수 있다는 것이다. 이를 해결하는 방법은 (n(b) - n(a-1) + R) % R과 같이 만들면 정확한 답을 구할 수 있다. 문제에 주어진 입력에 대한 답은 <표 5>와 같으며, 최종 코드는 <리스트 4>와 같다.

<리스트 4> a~b까지 박수 횟수 프로그램 (100점 풀이)
#include < iostream>
#define N 100005
#define R 20150523
using namespace std;int ans1,ans2,A[N],B[N],C[N],D[N],X[N],Num[N];
string a,b;
void make_table(int len) {
int i;
B[0] = 1;
for(i=1; i< =len; i++) {
A[i] = (A[i-1]*10 + B[i-1]*3) % R;
B[i] = (B[i-1]*7) % R;
}
C[0] = 1;
for(i=1; i< =len; i++) {
C[i] = (C[i-1]*1 + D[i-1]*6) % R;
D[i] = (C[i-1]*3 + D[i-1]*4) % R;
}
X[0] = 1;
for(i=1; i< =len; i++) {
X[i] = (X[i-1]*10) % R;
}
}
int calc(int len) {
int i,j,k,s,s2,sum,to;
s = s2 = sum = 0;
for(i=1; i< =len; i++) {
if(Num[i]==3 || Num[i]==6 || Num[i]==9) break;
}
k = i;
to = min(k,len);
for(i=1; i< =to; i++) {
for(j=0; j < Num[i]; j++) {
if(j==3 || j==6 || j==9) s += X[len-i];
else s += A[len-i];
s %= R;
}
}
for(i=1; i< =to; i++) {
for(j=0; j< Num[i]; j++) {
if(j==3 || j==6 || j==9) continue;
if((sum+j)%3 == 0) s += C[len-i];
else s += D[len-i];
s %= R;
}
sum = (sum+Num[i]) % 3;
}
s--;
for(j=k+1; j< =len; j++) {
s2 = (s2*10+Num[j]) % R;
}
s += s2;
if(k< =len || sum%3==0) s++;
return s%R;
}
int main() {
int i;
cin >> a >> b;
make_table(b.size());
for(i=0; i< a.size(); i++) Num[i+1] = a[i] - '0';
for(i=a.size(); Num[i]==0; i--) Num[i] = 9;
Num[i]--;
ans1 = calc(a.size());
for(i=0; i< b.size(); i++) Num[i+1] = b[i] - '0';
ans2 = calc(b.size());
cout < < (ans2-ans1+R) % R;
return 0;
}

이 풀이는 A,B,C,D,X 배열을 구하는 make_table() 함수에서 O(10만)이 되고, 1~p까지 박수의 횟수를 구하는 calc() 함수에서는 O(10만*10) = O(100만)이 되기 때문에 제한시간 1초 안에 충분히 답을 얻을 수 있다.

출처 : 마이크로소프트웨어 11월호

제공 : 데이터 전문가 지식포털 DBguide.net