[Inflearn] 3의 개수는?(large)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand the problem

  2. Redefine the problem + abstract

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

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

  5. Carry out the plan

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

#. Solve

  1. 이 문제는 전 문제와는 다르게 제목에서부터 large 라고 되어있을 뿐만 아니라,

     최대 N도 1,000,000,000 이다.. 결코 그냥 풀어서는 안 될..!

     생각을 좀 해보고 풀어야 할 문제이다.

     전에 유사한 문제를 풀었을 때, 해결법이 떠오르지 않아 결국 small 문제처럼 풀어냈었는데

     여기서 또 만날 줄이야.. 마치 외나무다리처럼..?

    

     숫자의 총 개수 문제에서 풀었던 방식과 비슷하게 시도해보자.

     각 자리수대에서의 3의 개수를 세보면

     1 ~ 9 : 1 개

     10 ~ 99 : 19 개

     100 ~ 999 : (1+19) x 9 + 100 = 280개 (300대에서는 3이 100개 추가)

     1000 ~ 9999 : (1 + 19 + 280) x 9 + 1000 = 3700개 

     10000 ~ 99999 : (1 + 19 + 280 + 3700) x 9 + 10000 = 46000개

     N = 12345 일 때, (N을 가정하고 손로직으로 짜보는게 더 접근하기 쉬운 것 같다) 

     전 문제의 코드에 넣어서 결과를 먼저 확인해보았다. res = 4721

     N이 9보다 클 경우, res += 1

     N이 99보다 클 경우, res += 19

     N이 999보다 클 경우, rest += 280

     N이 9999보다 클 경우, rest += 3700

     N이 99999보다는 작군,

     지금까지 개수를 다 더해보면, 1 + 19 + 280 + 3700 = 4000 이다.

     우선 코드를 돌려보면 10000 ~ 12345 까지 3의 개수는 721 개이므로 이렇게 접근하는게 맞긴 한 것 같다.! 휴..

     (정 안 풀리면 이렇게 주먹구구식으로 짠 후에 값을 확인하면서 풀어가는 방법도 좋다. 최적화(?)라고 할 수도 있겠네. 안 풀린다고 바로 해결법을 보는 것 보다는 끝까지 어떻게서든 찾아보는 방법이 중요하지!)

    이제 10000 ~ 12345 까지 3의 개수를 세는 것이 문제로다.

    그냥 돌려버려?! 라고 생각하는 순간 또 다시 시간초과의 늪으로.. 

    여기서는 12345에서 10000을 빼주고 2345 까지의 3 개수를 구하면 될 것 같은데

    N이 2345일 경우로 다시 해보아야 하려나..

    위 공식을 다시 적용해보면 res += 1 + 19 + 280

    res = 4280

    여기서 다시 1000을 빼고 돌린다..?

    너무 연산이 많이지는데ㅠㅠ

2. 다시 생각해보자.. 너무 앞 문제에 맞추려고 했나?

   이 문제는 이 문제이므로 이 문제에 맞춰야 하는데..

   1 ~ 9 : 1 개

   10 ~ 99 : 19 개

   100 ~ 999 : (1+19) x 9 + 100 = 280개 (300대에서는 3이 100개 추가)

   1000 ~ 9999 : (1 + 19 + 280) x 9 + 1000 = 3700개 

   10000 ~ 99999 : (1 + 19 + 280 + 3700) x 9 + 10000 = 46000개

  

   각 자리수에 3이 몇 개 있는지 알아내면 되는게 포인트인데

   다시 N = 12345 일 때,

   일의 자리는 얼마 안 되니까 5까지 3의 개수를 찾아본다. = 1 개

   십의 자리는 1~9까지가 4개 있으므로 1 x 4 = 4개, 단 3보다 크기 때문에 + 10 = 14 개

   백의 자리는 10~99까지가 3개 있으므로 19 x 3 = 57개, 단, 3과 같기 때문에 + 46 = 101 개

   천의 자리는 100~999까지가 2개 있으므로 280 x 2 = 560개, 3보다 작으므로 패스

   만의 자리는 1000~9999까지가 1개 있으므로 3700 x 1 = 3700개, 3보다 작으므로 패스

3. 생각보다 너무 안 풀리네..

   강사님의 힌트를 결국 얻게 되었다.

   

   마찬가지로 N = 12345 일 때,

   일의 자리는 3보다 크므로 일의 자리에서 3이 0000 ~ 1234 개 만큼 나온다. = [ 1235 개 ]

   (3을 고정으로 두었을 때, 앞에 00003 ~ 12343 까지 계속 1의 자리에 3이 나오기 때문!)

   1 2 3 4 (5)

   0 0 0 0 (3)

   ...

   1 2 3 4 (3)

   [ 1 2 3 5 가지 ] 

   십의 자리도 3보다 크므로 십의 자리에서 3이 000 ~ 123 개 만큼 나온다.

   LeftNum 에서 000부터 123까지 124번 나오고 일의 자리에서도 0~9가 반복되므로 124 * 10 을 해주면 = [ 1240 개 ]

   글로 설명하기가 굉장이 어렵네..

   1 2 3 (4) 5

   0 0 0 (3)  0 ~ 9

   ...

   0 0 1 (3)  0 ~ 9

   ...

   1 2 3 (3) 0 ~ 9

   [ 1 2 4 x 10 = 1240 가지]

   백의 자리가 이번에는 3과 같으므로 200대까지 우선 구해준 후 십의 자리까지 나올 수 있는 수를 더해준다.

   1 2 (3) 4 5   

   0 0 (2)  00 ~ 99

   ...

   1 1 (2) 00 ~ 99

   ...

   1 2 (3) 00~45

   [ 1 2 x 1 0 0 + 4 6 = 1246 가지]

   

  천의 자리는 3보다 작으므로, 

  1 (2) 3 4 5

  0  3  000 ~ 999

  ...

  1 2 ,,,

  [ 1 x 1000 가지 ]

  지금까지의 수를 다 더해보면 1235 + 1240 + 1246 + 1000 = 4721

  구현하기 전에 각 자리수가 3보다 작은지, 같은지, 큰지에 따라 계산을 다르게 식을 사용해야 한다.

  p > 3 : (LeftNum + 1) * t(자리수)

  p = 3 : (LeftNum) * t + (RightNum + 1)

  p < 3 : (LeftNum) * t

 

  복잡할 것 같지만 코드로 구현해보자!

#. Code

#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    //freopen("input.txt", "rt", stdin);
 
    int n, cnt = 0, t = 1, p, ln = 1, rn = 1;
 
    scanf("%d", &n);
 
    while (n / t * 10)
    {
        ln = n / (t * 10);
        rn = n % t; 
        p = (n % (t * 10)) / t;
 
        if (p > 3)
            cnt += (ln + 1)*t;
        else if (p == 3)
            cnt += ln*t + rn + 1;
        else
            cnt += ln*t;
 
        t *= 10;
    }
 
    printf("%d\n", cnt);
 
    return 0;
}

  ln      rn    p    cnt   // LeftNum, RightNum, point, count 

 1234    0    5    1235

 123     5    4    1235 + 1240

 12     45    3    1235 + 1240 + 1246

 1     345    2    1235 + 1240 + 1246 + 1000

식은 위 설명에서 명시한 그대로 사용하였고,

ln, rn, p 를 구하는 과정에서 계속 꼬여서 디버깅을 하면서 풀어나갔다.

위에 변수명과 값들을 적은 것 처럼 적어가면서 하면 어떤 변수가 잘못 되었고, 어디서 제대로 작동을 안 하는지 알 수 있다.

#. Other code

#include<stdio.h>
 
int main(){
    int n, lt=1, rt, cur, k=1, res=0;
 
    scanf("%d", &n);
 
    while(lt!=0){
        lt=n/(k*10);
        rt=n%k;
        cur=(n/k)%10;
 
        if(cur>3) res=res+((lt+1)*k);
        else if(cur==3) res=res+((lt*k)+(rt+1));
        else res=res+(lt*k);
 
        k=k*10;
    }
 
    printf("%d\n", res);
 
    return 0;
}
 

강사님의 힌트를 얻고 풀었기 때문에 로직은 같을 수 밖에 없다.. 여기서 구현의 차이가 발생하겠지.. 하핳

현재 자릿수의 값을 구할 때, 위 코드는 (n/k)%10 로 간단하게 구하였는데 나는 (n % (k*10)) / k) 뭐 이렇게 복잡하게 구했는지..ㅋㅋㅋ

N = 12345 에서 k = 100 이라면, 

현재 자릿수는 3이 나와야 한다.

(n/k)%10 를 적용해보면 3이 잘 나오군..

(n % (k*10)) / k) 도 잘 나오긴 하지만 엄청 꼬아서 구한 것 같다. 

머얼리 돌아가지 말고 가까서 찾으라..

이 문제도 결국 힌트를 얻고 풀었으니, 나중에 다시 풀어봐야지..

#. Result

  - Input --------------------------------------------------------

15

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

  - Output --------------------------------------------------------

2

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