백준 문제풀이 : (1790) 수 이어 쓰기 2 - c/c++

문제 : https://www.acmicpc.net/problem/1790

1790번: 수 이어 쓰기 2

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	64 MB	Gold 5	수학 / 구현

 

 

문제

 

풀이

수가 십의 제곱 단위로 커지는 구간 마다 수와 숫자의 개수는 다음과 같다.

 

한 자릿수 범위 (1~9)

수 : 9개 / 숫자 : 9개

 

두 자릿수 범위 (10~99)

수 : 90개 / 숫자 : 180개

 

세 자릿수 범위 (100~999)

수 : 900개 / 숫자 : 2700개

 

이 규칙을 다음과 같은 공식으로 정리할 수 있다.

 

수의 개수 :  9 * 10의 (자릿수-1) 승

숫자의 개수 : 9 * 자릿수 * 10의 (자릿수-1) 승

 

문제에서는 k번째 숫자를 구하는게 목적이므로, 루프를 돌려 k에서 각 자릿수 범위 마다의 숫자 개수를 차감해준다. 

차감이 끝난 후의 k를 kk라고 명명한다. 루프가 끝난 후, kk는 계산한 자릿수 범위 내에서의 위치가 된다. 

따라서 해당 자릿수 범위 내의 최솟값에 "(kk-1)/자릿수" 값을 더해주면 k를 가진 수가 무엇인 지 알 수 있다.

 

이 수를 num이라 했을 때, num에서 몇 번째 숫자가 정답인 지는 % 연산자를 활용해 구한다.

 

ex) n=20 , k=23

루프를 돌려 k에서 자릿수 범위마다의 숫자 개수를 차감해준다. 

loop1) 23-9 = 14

loop2) 14-180 = (음수 값이 됨. 따라서 반복 종료)

 

위 계산 결과 k의 자릿수는 2이다. 그리고 kk= 14 인 상태에서 반복이 종료되었다.

 

따라서 k번째 숫자를 가진 수(num)는 "10의 0(자릿수-1)승 + (kk-1)/자릿수" 가 되어, 10+6 = 16이 된다.

 

num에서 몇 번째 숫자가 정답인 지는 (kk-1)%자릿수 하여 알 수 있다. 하지만 수의 숫자를 0, 1, 2, 3.. 인덱스 순으로 접근해야 하므로 < num의 "자릿수-(kk-1)%자릿수"번째 숫자> 가 정답이 된다. 

 

 

코드 작성

#include <iostream>

using namespace std;

long long powNum(int num, int quot) {
    if (quot==0) return 1; 
    return num*powNum(num, quot-1);
}

long long getResult(int num, int cipher) { //숫자에서 자리에 있는 수 가져오기
    return num/powNum(10, cipher-1)%10;
}

int main() {
    long long n, k;
    scanf("%lld %lld", &n, &k);
    
    long long kk=0; //루프 문 내에서 변경되는 k의 값을 저장한다.
    long long cc=0; //루프 문 내에서 변경되는 c(반복횟수=자릿수)값을 저장한다.
    for (long long c=1 ; k>0 ; c++) { //k의 값이 음수가 되면 종료.
        kk=k; //k의 음수 이전 값을 구해야 하므로 마이너스 연산 전 kk에 따로 저장한다.
        cc=c; 
        k-=(9*c*powNum(10, c-1)); // 9, 180, 2700 순으로 마이너스 된다.
    }
    long long num=powNum(10, cc-1)+(kk-1)/cc; // k번째 숫자를 갖고 있는 수를 구한다.
    
    long long result = getResult(num, cc-(kk-1)%cc); //num의 앞에서 몇 번째 수가 정답인지 계산
    if (num>n) result=-1; //num이 n보다 크다면 범위 초과이니 -1 출력
    
    printf("%lld", result);
}

 

 

END.