[BOJ] 17614번. 369

#. Problem

https://www.acmicpc.net/problem/17614

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

     - 1 이상의 정수 N에 대하여 369 게임을 N까지 규칙을 지키며 진행된다면 그때까지 듣게 되는 박수의 총 횟수

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

     - N 은 1 <= N <= 10^6

     - 1 초

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 1 ~ 9 까지 3번의 박수

 10 ~ 19 까지 3번의 박수

 ...

 30 ~ 39 까지 13번의 박수

즉, 10 자리가 3, 6, 9 일 경우 13번 박수를 치고, 그 외에는 3번의 박수를 친다.

input 이 14일 경우, (3, 6, 9), (13) 총 4회 박수를 치고

input 이 36일 경우, (3, 6, 9), (13, 16, 19), (23, 26, 29), (30, 31, 32, 33, 33, 34, 35, 36, 36) 총 18회 박수를 친다.

input 이 100일 경우 10의 자리가 3, 6, 9 인 경우 3 x 13 = 39 와 그 외 7 x 3 = 21 을 합하여 60회 박수를 치게 된다.

1. input 이 10의 자리일 경우, 해당 자리수 (ex. N = 66) 60대는 제외하고 50대까지 먼저 구해주야할 것 같다.

(N - (N % 10)) - 1 = 59 

그 다음, 59 / 10 + 1 을 계산하고, 결과 6 x 3(1의 자리일 경우도 포함) 을 해주면 기본적으로 18회의 박수를 치게 된다.

여기서 10의 자리에 3, 6, 9 가 포함되어있는지 확인을 해주어야 한다. 59 / 10 / 3 = 1 이므로 3의 배수가 1번 포함되므로,

59 / 10 / 3 * 10  = 10 만큼 더해주면 된다. + 10 회, 여기까지 0 ~ 59 까지 박수 횟수를 구했다.

2. 그 다음, 나머지 (60 ~ 66) 박수 횟수를 계산해주면 된다.

우선, N / 10 % 3 == 0 을 연산하여 나머지 구간의 10의 자리가 3의 배수인지 확인을 해준다. 

3의 배수일 경우, 60 ~ 66 까지 기본적으로 N % 10 + 1 = 7 회 박수를 쳐줘야 한다. 

마지막으로 일의 자리 수를 확인해주면 N % 10 / 3 = 2 이므로, + 2회 만큼 더해주면 된다. (33, 66 일 경우 2번 박수를 치므로)

만일, 10의 자리가 3의 배수가 아니라면 (ex. 50 ~ 56) 56 % 10 / 3 = 2 만큼 더해주면 된다.

결과적으로, N 이 66일 경우 18 + 10 + 7 + 2 = 37 회 박수를 치게 된다.

위 방법이 틀린 것은 아니지만, 훨씬 간단하고 단순하게 풀 수 있는 문제였는데 너무 어렵게만 생각했던 것 같다..

우선 최대 N 은 10^6 = 1,000,000 이다. 즉, 1초에 1억번 연산을 할 수 있기는 양이기 때문에 제한 시간 1초 내에 주어진 N을 모두 계산할 수 있다.

그러므로, 1부터 N 까지 하나하나 비교하며 count 해줘도 전혀 시간초과가 발생하지 않는다는 것이다.

정말 단순하게 

1부터 N까지 순차적으로 N % 10 이 3 or 6 or 9 일 경우 count 를 증가시켜주고, N / 10 을 해주는 루프를 구현한다.

이것은 number 의 일의 자리 수 부터 3, 6, 9 가 있는지 계속 확인해주며 count 를 증가시켜주는 방식이다.

#. Code

#include <iostream>
 
using namespace std;
 
#define init() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
 
int N, i = 1, cnt = 0;;
 
int main()
{
    init();
 
    cin >> N;
 
    do
    {
        int temp = i;
 
        while (temp > 0)
        {
            cnt = (temp % 10 == 3 || temp % 10 == 6 || temp % 10 == 9) ? cnt + 1 : cnt;
 
            temp = temp / 10;
        }
 
        i++;
    } while (i <= N);
 
    cout << cnt;
 
    return 0;
}

#. Other Codes

/*
 * reference : xodnr6334
 */
 
#include <cstdio>
 
using namespace std;
int N;
 
int main()
{
    int rst = 0;
    int arr[7] = { 0, };
 
    scanf("%d", &N);
    
    // N의 각 자리에 해당하는 숫자를 배열에 저장
    arr[0] = N % 10;
    arr[1] = (N % 100) / 10;
    arr[2] = (N % 1000) / 100;
    arr[3] = (N % 10000) / 1000;
    arr[4] = (N % 100000) / 10000;
    arr[5] = (N % 1000000) / 100000;
    arr[6] = (N % 10000000) / 1000000;
    
    // 일의 자리에 3, 6, 9 가 있는 경우를 먼저 count
    rst += (N / 10) * 3 + arr[0] / 3;
 
    for (int i = 1; i < 7; i++) 
    {
        int p = 10;
    
        // 몇 번째 자리수인지
        for (int j = 1; j < i; j++)
           p *= 10; 
        
        // 해당 자리수가 3, 6, 9 일 경우,
        if (arr[i] == 3 || arr[i] == 6 || arr[i] == 9)
            rst += (N / (10 * p)) * 3 * p + (arr[i] / 3 - 1) * p + N % p + 1;
        else
            rst += (N / (10 * p)) * 3 * p + (arr[i] / 3) * p;
    }
 
    printf("%d", rst);
 
    return 0;
}

(18~24) 에서 각 자리에 해당하는 숫자를 미리 계산해주고,

(38~41) 에서 해당 자릿수에 오기까지 포함되는 3, 6, 9 의 개수를 한 번에 연산해주면서 시간을 단축시킬 수 있던 것 같다.