ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 1081 합
    알고리즘 문제/math 2019. 3. 9. 16:28

    문제보기

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


    L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오.

     U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다.


    풀이

    이 문제는 철저하게 수학 문제이다. 나는 접근방법을 보고나서야 풀 수 있었다. 

    접근법은 10단위로 생각할 것.

    10 ~ 29 까지  1 단위 자리의 0~ 9 의 발견횟수는 각각 (2-1+1) 이다. 이를 기준으로 계산한다.

    만약 Lower, Upper 구간이 0이 아니라고 해보자. 이 경우 0 으로 맞춰줘야한다. 

    - Lower, Upper 도 1씩 올리던,

    - Lower, Upper 를 1씩 내리던,

    - Lower 를 1씩 내리고, Upper를 1씩 올리던 

    - Lower 를 1씩 올리고, Upper를 1씩 내리던 

    해줘야할 것 인데 어떤게 맞을까?


    Lower 를 1씩 올리고, Upper를 1씩 내려서 맞춰주자. 그래야 우리가 원하는 알고리즘이 수행된다.

    Lower, Upper를 0으로 이동시키는 동안 그 Lower와 Upper가 가지고 있는 숫자들을 base=1씩 증가시켜준다. 

    그리고 (Lower/10 - Upper/10)*base 만큼 0~9를 증가시켜준다. 


    그리고 Lower, Upper의 자리수를 줄여준다. 이때, 자리수를 줄이는 것은 이 알고리즘에서 무엇을 뜻하냐면 base를 10 곱해주는 것이다.

    알고리즘이 체크하는 자리수가 증가한 것이기 때문에 발견횟수가 10씩 곱해준것만큼 늘어난다고 생각해야한다.

    예로, 10 ~ 19 에서 1자리수의 0~9 발견횟수는 base = 1이다. 

    100 에서 199 를 생각해보자. 1 자리수의 0 ~9 발견횟수는 (19 -10 +1) = 10 회이다. 

    그리고 자리수를 줄여주었을때 10 에서 19가 된다. 이때 1 자리수(사실은 10자리수)의 0~9 발견횟수는 10회이다.  왜냐하면 100 에서 199 사이의 수 110 과 119만 고려하자. 10의 자릿수에서 1의 발견횟수는 10회이다. 

    이것이 반복적으로 수행되면서 알고리즘은 Lower > Upper 가 되는 순간 끝이난다.


    흥미로운 문제다. 

    swexpert 

    https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1081.cc

    '알고리즘 문제 > math' 카테고리의 다른 글

    cf 585div2 B. The Number of Products  (0) 2019.09.18
    삼각형의 면적 구하기, 백준 2166 다각형의 면적  (0) 2019.03.20
    백준 1081 합  (0) 2019.03.09
    codeforces 1060C Maximum Subrectangle  (0) 2018.12.13
    908C New Year and Curling  (0) 2017.12.31
    900B Position in Fraction  (0) 2017.12.15

    댓글 0

Designed by Tistory.