3의 배수 판정

문제 출처 http://koistudy.net/?mid=prob_page&NO=600

이진수를 십진수로 변환해서 %(나머지) 연산자를 쓰면 될 것 같지만 자릿수가 최대 10만이다. 정수 변수는 보통 32비트고 많아봤자 128비트까지이므로 불가능하다.

처음에는 3의 배수들을 이진수로 바꿔 나열하고 패턴을 찾아보려 했지만 3 x 2^n 꼴인 수들이 오른쪽에 0이 하나씩 늘어나는 것 빼고는 딱히 패턴을 찾을 수 없었다.

3 -> 11₂

6 -> 110₂

9 -> 1001₂

12 -> 1100₂

15 -> 1111₂

...

다음으로 입력받는 수를 쪼개서 처리해보려 했다. 예를 들어 a = b + c인데 b와 c가 3의 배수이면 a도 3의 배수다. 가령 입력이 110011₂이라면 11₂= 3으로 3의 배수이므로 없애고 남는 1100₂을 처리한다. 0이 하나 붙으면 2배가 되는 것인데 3의 배수 판정에 필요 없으므로 가장 오른쪽의 0들은 나오는 족족 제거해도 된다. 0 두 개를 제거하고 남는 11₂도 3의 배수이므로 110011₂은 3의 배수다.

하지만 이 방식 역시 3의 배수가 아닌 부분열이 길어지면 정수 변수의 표현 범위를 넘어선다. 테스트 입력을 운 좋게 통과할 지는 몰라도 좋은 방법은 아니라 코딩하지 않았다.

이번에는 학교에서 배운 십진수에서 3의 배수 판정법을 고려해봤다. 십진수 n의 각 자릿수를 모두 더해서 3의 배수면 n은 3의 배수다. 예를 들어 1531623은 1 + 5 + 3 + 1 + 6 + 2 + 3 = 21이므로 3의 배수다. 증명은 간단한데 (0 ≤  ≤ 9인 정수) 일 때 이 3의 배수면  이므로 n도 3의 배수다.

이제 이진수에서 3의 배수를 생각해보자. 이진수 n을 전개한 다음 각 항을 3의 배수로 만들면서 발생한 항들을 따로 모은다.

(변수들은 각각 0 또는 1)

왼쪽 괄호 안의 합은 항상 3의 배수고 오른쪽 괄호 안의 합이 3의 배수면 n 역시 3의 배수다. 앞에서 몇 자리만 이렇게 분리해봤는데 오른쪽 항을 이렇게 항상 -와 +가 번갈아나오게 분리하여 만들 수 있는지를 증명해아 한다. 홀수번째 항은 3k+1, 짝수번째 항은 3k-1꼴(k는 정수)이면 위와 같은 형태로 항상 분리할 수 있다.

홀수번째 항을 증명해보자. 이 3k+1이라 가정한다. (b는 0 또는 1, n은 음이 아닌 정수) n을 n+1로 치환해서 이므로 은 3(k+1)+1로 표현할 수 있다. 짝수번째 항도 같은 방식으로 증명할 수 있다.

위 방법을 코드로 작성해서 테스트를 돌렸고 오류 없이 통과했다.

#include <stdio.h>

void main() {

  int n, a=0, sgn;

  scanf("%d\n", &n);

  sgn = n&1 ? 1 : -1;

  while(n--){

    a += sgn * (getchar() - '0');

    sgn = -sgn;

  }

  puts(a%3 ? "False" : "True");

}

코드가 몇 바이트일까 궁금해서 공백과 줄바꿈을 다 없애보았고 1등은 100바이트던데 내 건 111바이트가 나왔다.

main(){int n,a=0,s;scanf("%d\n",&n);s=n&1?1:-1;while(n--){a+=s*(getchar()-'0');s=-s;}puts(a%3?"False":"True");}

더 줄이기 귀찮음