코드업(codeup) 3710 : 369 게임 3 (Large Test Case) C언어

▶문제 : 369 게임 3 (Large Test Case) (codeup.kr)

 

▶코드 작성

#include <stdio.h>

int arr[100000001];

int main()
{
    int a, b, cnt = 0;

    scanf("%d %d", &a, &b);

    arr[3] = 1;
    arr[6] = 1;
    arr[9] = 1;//한자리 수 박수칠 개수 입력

    for (int i = 13; i <= b; i++)//9다음으로 박수치는 숫자 13부터 반복문 시작
    {
        if ((i % 10) % 3 == 0 && i % 10 != 0) arr[i]++;//i의 일의자리 숫자가 3의 배수일 때 +1
        arr[i] += arr[i / 10];//일의자리 숫자를 제외한 나머지 수 = i/10 의 박수칠 개수 더함
    }

    for (int i = a; i <= b; i++) cnt += arr[i];//a부터 b까지의 박수 칠 개수 총합

    printf("%d", cnt);

    return 0;
}

 

▶해석

1~9인 한자리 숫자들 중 박수 칠 수 3,6,9를 미리 1씩 입력해주었다. 반복문으로 9 다음으로 박수 칠 수인 13부터 b까지 반복하여 i를 10으로 나눈 나머지 수가 일의 자리 수이고, 그 수를 3으로 나눈 나머지가 0일 때 0,3,6,9이고, 0을 제외시키면 3,6,9이므로 배열의 i자리인 arr [i]를 +1 해주었다. 그리고 일의 자리 수를 제외한 나머지 수는 i/10인 정수이므로 arr [i/10]에서 박수 칠 개수를 가져와 arr [i]에 더해주었다.

 예를 들어 arr [3]=1이고 i=33을 구한다고 하면 10으로 나눈 나머지가 3이고 3의 배수이므로 arr [33]++ 해주고, i/10의 정수는 3이므로 arr [3]=1이니 arr [33]에 더해주면 arr [33]은 2가 된다. 그러므로 33은 2번 박수를 쳐야 하는 것이 된다. i=333을 구한다면 일의 자리 숫자가 3이므로 arr [333]++ 해주고, 일의 자리 숫자를 제외한 수는 33이므로 arr [33]은 방금 구한 것처럼 2라는 결론이 나왔기에 arr [333]에 더해주면 3이 된다. 333은 3번 박수 치는 것이 맞다.

나도 처음엔 나만의 계산식으로 복잡한 계산하에 결과를 바랐지만 예외상황이 있어 해결하는데 시간이 오래 걸렸다. 그래서 댓글을 찾아보니 admin님의 조언으로 배열을 이용하여 풀 수 있었다.