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

C++ 자릿수 DP로 범위 내 숫자 d가 정확히 K번 등장하는 수의 개수 구하기

시작 값(start)부터 끝 값(end)까지의 정수 범위와 두 변수 k, d가 주어졌을 때, 해당 범위 안에서 숫자 d가 정확히 k번 등장하는 수의 개수를 구하는 것이 이번 문제의 목표입니다. 이 문제는 자릿수 DP(Digit DP) 기법을 활용하면 효율적으로 해결할 수 있습니다.

예시

입력 - int start = 10, int end = 100, d = 4, K = 2

출력 - 숫자 d가 정확히 K번 등장하는 범위 내 수의 개수: 1

설명 - 범위는 10부터 100까지입니다. 이 범위에서 숫자 4가 정확히 2번 등장하는 수는 44 하나뿐이므로 개수는 1입니다.

입력 - int start = 10, int end = 100, d = 6, K = 1

출력 - 숫자 d가 정확히 K번 등장하는 범위 내 수의 개수: 8

설명 - 범위는 10부터 100까지입니다. 이 범위에서 숫자 6이 정확히 1번 등장하는 수는 16, 26, 36, 46, 56, 76, 86, 96으로 총 8개입니다. 단, 66은 숫자 6이 k번보다 많이 등장하므로 제외됩니다.

프로그램에 적용된 접근 방식

  • start부터 end까지의 정수 범위를 준비하고 변수 d와 k를 선언해 값을 입력합니다. 이후 세부 처리를 위해 함수에 데이터를 전달합니다.
  • vec라는 이름의 vector 타입 변수를 생성합니다.
  • val(start에 담긴 값)이 0이 될 때까지 while 루프를 돌며, 루프 안에서 val % 10 값을 벡터에 push하고 val을 val / 10으로 갱신해 각 자릿수를 분리합니다.
  • STL의 reverse 함수에 vec.begin()과 vec.end()를 인자로 넘겨 자릿수 배열을 원래 순서대로 복원합니다.
  • memset을 사용해 메모이제이션 배열 arr의 모든 값을 -1로 초기화합니다.
  • set_total(0, 0, 0, 0, vec)을 호출해 그 결과를 반환합니다. 이 함수는 조건을 만족하는 수의 개수를 재귀적으로 계산합니다.

set_total 함수의 동작

  • place가 벡터의 크기와 같으면 temp == K인지 확인한 뒤, 참이면 1, 거짓이면 0을 반환합니다.
  • arr[place][temp][val][rem]의 값이 -1이 아니라면 이미 계산된 결과이므로 그 값을 그대로 반환합니다(메모이제이션).
  • 결과를 저장할 count 변수를 선언합니다.
  • temp_2 변수를 선언하고, val이 1이면 9로, 그렇지 않으면 vec[place]로 설정합니다. 이는 현재 자리에서 선택 가능한 최대 숫자를 의미합니다.
  • i를 0부터 temp_2까지 반복하는 for 루프를 실행하며, i가 d와 같고(d가 0이 아니거나, d가 0이면서 rem이 1인 경우) total을 1 증가시킵니다. 이 조건은 선행 0을 올바르게 처리하기 위한 것입니다.
  • total_2 변수를 선언하고 val 값으로 초기화합니다.
  • i가 vec[place]보다 작으면 total_2를 1로 설정합니다. 이는 이후 자릿수를 자유롭게 선택할 수 있음을 의미합니다.
  • count에 set_total의 재귀 호출 결과를 누적합니다.
  • arr[place][temp][val][rem] = count를 저장한 뒤 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

const int MAX = 20;
int arr[MAX][MAX][2][2];
int d, K;

int set_total(int place, int temp, int val, int rem, vector < int > vec) {
    if (place == vec.size()) {
        if (temp == K) {
            return 1;
        }
        return 0;
    }
    if (arr[place][temp][val][rem] != -1) {
        return arr[place][temp][val][rem];
    }
    int count = 0;
    int temp_2 = (val ? 9 : vec[place]);

    for (int i = 0; i <= temp_2; i++) {
        int total = temp;
        if (i == d) {
            if (d != 0 || (!d && rem)) {
                total++;
            }
        }
        int total_2 = val;
        if (i < vec[place]) {
            total_2 = 1;
        }
        count += set_total(place + 1, total, total_2, rem || (i != 0), vec);
    }
    return arr[place][temp][val][rem] = count;
}

int occurrence_d(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 set_total(0, 0, 0, 0, vec);
}
int main() {
    int start = 10;
    int end = 100;
    d = 4, K = 2;
    int count = occurrence_d(end) - occurrence_d(start - 1);
    cout << "Count of Numbers in a Range where digit d occurs exactly K times are: " << count;
    return 0;
}

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

출력

Count of Numbers in a Range where digit d occurs exactly K times are: 1

이처럼 자릿수 DP를 활용하면 범위 내 모든 수를 일일이 검사하지 않고도 조건을 만족하는 수의 개수를 빠르게 계산할 수 있습니다. 핵심 아이디어는 [start, end] 범위의 답을 occurrence_d(end) - occurrence_d(start - 1)로 구하는 것이며, 메모이제이션 덕분에 중복 계산 없이 효율적인 시간 복잡도로 문제를 해결할 수 있습니다.