외부문제를 좀 풀었는데 알고리즘 힌트 좀 부탁드립니다

  • damian
    damian

    1부터 10^9까지의 범위에서
    랜덤한 범위를 정해서 그 범위안의 숫자들을
    각 자리값마다 합산해서 출력하는 문제인데요

    ex) 8~12까지의 범위라면
    8+9+(1+0)+(1+1)+(1+2)
    같은 형식으로 계산.

    저 같은 경우 단순하게 10진수 각 자리를 나머지를 이용해서 분리한 후 더해가며 계산했는데, 답은 나오지만 속도가 너무 느리더군요...

    예를 들어 X라는 값이 들어오면

    Sum = X%10; X /= 10;

    같은 형식으로 범위에서 제일 작은 값부터 1씩늘려가면 계산했습니다

    좀 더 빠르게 해결할 수 있는 방법이 있을것 같은데
    힌트 좀 부탁드립니다.

    친구들이랑 고민하다가 수열 일반식이 세워질것 같아서 그쪽으로 고민도 해봤는데 힘들더군요 :D

    그럼 조언 부탁드립니다~


    9년 전
3개의 댓글이 있습니다.
  • VOCList
    VOCList

    func(a) = 0 ~ a 까지의 위 연산 결과를 리턴해주는 함수라고 생각해봅시다.
    그렇다면 주어진 범위가 s ~ e 일 때 답은 func(e) - func(s - 1) 임이 자명합니다.

    이제 func(a)를 구하면 되는데요.
    제일 큰 자릿수부터 채워 나가면 어렵지 않게 구할 수 있을 것 같습니다.
    예를 들어 func(324)를 계산해볼게요.
    먼저 0 ~ 299까지의 합: func(99) + (func(99) + 1 * 100) + (func(99) + 2 * 100)
    300 ~ 319까지의 합: func(9) + (func(9) + 1 * 10) + 3 * 20
    320 ~ 324까지의 합: func(4) + 2 * 5 + 3 * 5


    9년 전 link
  • VOCList
    VOCList

    사전 연산을 통해서 func(9), func(99), func(999), ... 를 빌드해두면 빠르게 할 수 있겠지요. 이들을 빌드하는 것 또한 위와 같은 방법으로 해볼 수 있습니다. func(9)를 알면 func(99)를 구할 수 있고 그 다음은 func(999) ... 와 같이 계속 구해 나갈 수 있으니까요.


    9년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    http://algospot.com/forum/read/719/ 이거에 500pt 문제 해설을 보시면 감을 좀 잡으실 수 있을 것 같습니다.


    9년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.