Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 특정 범위에서 0이 아닌 자릿수가 K개 이하인 수의 개수 구하기

정수 범위의 시작 값(start)과 끝 값(end), 그리고 정수 k가 주어졌을 때, 이 범위에 속한 수 중에서 0이 아닌 숫자(non-zero digit)의 개수가 k개를 초과하지 않는 수가 몇 개인지 계산하는 것이 이번 문제의 목표입니다.

문제 예제

입력 - int start = 50, end = 100, K = 2;

출력 - 범위 내에서 0이 아닌 숫자가 K개를 초과하지 않는 수의 개수: 50

설명 - 범위는 50부터 100까지이며 k는 2로 주어졌습니다. 50~99 사이의 모든 수는 두 자리 수이므로 0이 아닌 숫자가 3개 이상일 수 없고, 유일한 세 자리 수인 100 역시 0이 아닌 숫자가 1개뿐입니다. 따라서 범위 내 모든 수가 조건을 만족하며 개수는 50이 됩니다.

입력 - int start = 50, end = 100, K = 1;

출력 - 범위 내에서 0이 아닌 숫자가 K개를 초과하지 않는 수의 개수: 5

설명 - 같은 범위에서 k가 1이면, 0이 아닌 숫자가 최대 1개인 수만 조건을 만족합니다. 해당하는 수는 50, 60, 70, 80, 90이며 따라서 개수는 5입니다.

해결 접근 방식

이 문제는 모든 수를 하나씩 검사하는 대신, 자릿수 단위 동적 계획법(Digit DP)과 메모이제이션을 활용하면 효율적으로 해결할 수 있습니다. 프로그램의 동작 흐름은 다음과 같습니다.

  • start부터 end까지의 정수 범위를 만들고 k를 선언해 값을 입력한 뒤, 이후 처리를 위해 함수에 데이터를 전달합니다.
  • 벡터(vector) 타입의 변수 vec을 생성합니다.
  • val이 0이 될 때까지 while 루프를 돌면서 val % 10 값을 벡터에 push하고, val을 val / 10으로 갱신합니다. 이 과정에서 수의 각 자릿수가 벡터에 저장됩니다.
  • STL의 reverse 함수에 vec.begin()과 vec.end()를 인자로 전달해 자릿수 순서를 뒤집습니다.
  • memset을 사용해 배열 arr의 모든 값을 -1로 초기화합니다. 이 배열은 메모이제이션(계산 결과 캐싱)에 사용됩니다.
  • 각 자릿수가 0인지 아닌지를 판단하는 함수 check_val(0, 0, 0, vec)의 결과를 반환합니다.

check_val 함수의 내부 동작

  • place가 벡터의 크기와 같다면(모든 자릿수를 확인했다면), temp <= k일 때 1을, 그렇지 않으면 0을 반환합니다.
  • arr[place][temp][set_val]의 값이 -1이 아니라면 이미 계산된 결과이므로 해당 값을 그대로 반환합니다.
  • 결과를 저장할 변수 count를 선언하고 0으로 초기화합니다.
  • 변수 val을 선언하고, set_val이 1이면 9, 그렇지 않으면 현재 자릿수 vec[place]로 설정합니다. 여기서 set_val은 "현재까지 만든 수가 이미 상한값보다 작아 이후 자릿수를 0~9까지 자유롭게 선택할 수 있는지"를 나타내는 플래그입니다.
  • 0부터 val까지 FOR 루프를 실행합니다.
  • 루프 안에서 temp_2를 temp로 설정하고, i가 0이 아니면 temp_2를 1 증가시켜 0이 아닌 숫자의 개수를 기록합니다. 또한 temp_3을 set_val로 설정한 뒤, i가 vec[place]보다 작으면 temp_3을 1로 설정해 이후 자릿수의 제한을 해제합니다.
  • count에 재귀 호출 check_val(place + 1, temp_2, temp_3, vec)의 결과를 누적합니다.
  • 마지막으로 arr[place][temp][set_val]에 count를 저장한 후 반환하여, 동일한 상태에 대한 중복 계산을 방지합니다.

이 방식의 시간 복잡도는 자릿수 길이 × (K+1) × 2에 비례하므로, 범위가 매우 커도 빠르게 답을 구할 수 있다는 장점이 있습니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int arr[20][20][2];
int K;
int check_val(int place, int temp, int set_val, vector < int > vec) {
    if (place == vec.size()) {
        if (temp <= K) {
            return 1;
        }
        return 0;
    }
    if (arr[place][temp][set_val] != -1) {
        return arr[place][temp][set_val];
    }
    int count = 0;
    int val = (set_val ? 9 : vec[place]);
    for (int i = 0; i <= val; i++) {
        int temp_2 = temp;
        if (i != 0) {
            temp_2++;
        }
        int temp_3 = set_val;
        if (i < vec[place]) {
            temp_3 = 1;
        }
        count += check_val(place + 1, temp_2, temp_3, vec);
    }
    return arr[place][temp][set_val] = count;
}

int Not_more_k(int val) {
    vector < int > vec;
    while (val) {
        vec.push_back(val % 10);
        val = val / 10;
    }
    reverse(vec.begin(), vec.end());
    memset(arr, -1, sizeof(arr));
    return check_val(0, 0, 0, vec);
}
int main() {
    int start = 50, end = 100;
    K = 2;
    int count = Not_more_k(end) - Not_more_k(start);
    cout << "Count of Numbers in Range where the number does not contain more than K non zero digits are: " << count;
    return 0;
}

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

출력 결과

Count of Numbers in Range where the number does not contain more than K non zero digits are: 50

여기서 f(N)을 "N 이하의 수 중 조건을 만족하는 수의 개수"라고 정의하면, 구간 [start, end]의 답은 f(end) − f(start)로 계산됩니다. 시작 값도 결과에 포함하려면 Not_more_k(start - 1)을 사용하면 됩니다.