자연수 num이 하나 주어졌을 때, 이 문제는 num 이하의 자연수 중에서 자릿수를 어떤 방식으로 재배열(순열)하더라도 원래 수보다 항상 크거나 같아지는 수들의 개수를 계산하는 것입니다.
문제 정의와 조건
대상은 오직 자연수여야 합니다.
해당 자연수의 모든 가능한 순열(자릿수 재배열 결과)이 주어진 수 자신보다 크거나 같아야 합니다.
예시: num = 20일 때
1부터 20까지의 모든 수를 검사합니다.
한 자리 수 1, 2, 3, 4, 5, 6, 7, 8, 9는 자릿수가 하나뿐이므로 항상 조건을 만족합니다.
두 자리 수 중 11, 12, 13, …, 19 역시 자릿수를 뒤집어도(예: 12 → 21, 19 → 91) 항상 원래 수보다 크거나 같으므로 조건을 만족합니다.
따라서 답은 9 + 9 = 18개가 됩니다.
입출력 예시
입력 − num = 10
출력 − 개수는 9
설명 − 1, 2, 3, 4, 5, 6, 7, 8, 9는 어떻게 배열하든 자기 자신과 같으므로 모두 조건을 만족합니다.
입력 − num = 13
출력 − 개수는 12
설명 − 1~9에 더해 11, 12, 13이 조건을 만족합니다. 예를 들어 12의 순열인 21은 12보다 큽니다.
핵심 아이디어
어떤 수의 모든 순열이 자기 자신보다 크거나 같으려면, 자릿수가 왼쪽에서 오른쪽으로 비내림차순(예: 1349)으로 정렬되어 있어야 합니다. 반대로 어느 위치에서든 앞의 자릿수가 뒤의 자릿수보다 크다면(예: 21), 두 자릿수를 맞바꾼 순열이 원래 수보다 작아지기 때문입니다. 결국 이 문제는 "num 이하의 수 중 자릿수가 비내림차순으로 구성된 수의 개수"를 세는 문제와 동일합니다.
프로그램의 접근 방법
num 값을 입력받습니다.
한 자리 자연수는 항상 조건을 만족하므로 기본적으로 최소 9개가 존재합니다. 이에 따라 max_size를 9로 설정합니다.
1부터 9까지 반복문을 실행합니다.
반복문 안에서 list 타입 변수를 생성하고, i가 num 이하이면 i를 리스트에 삽입한 뒤 카운트를 1 증가시킵니다.
리스트를 뒤에서 앞으로 순회하며, 현재 수의 일의 자릿수부터 9까지의 숫자를 뒤에 붙여 새로운 수 temp를 만듭니다. 이렇게 하면 새로 만들어지는 수의 자릿수가 항상 비내림차순으로 유지됩니다.
temp가 num 이하이면 리스트 앞에 push하고 카운트를 1 증가시킵니다.
카운트를 반환하고 결과를 출력합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
// 모든 순열이 자기 자신보다 크거나 같은
// 자연수의 개수를 세는 함수
void count(int num){
int count = 0;
int max_size = 9;
for (int i = 1; i <= max_size; i++){
list<int> lists;
if (i <= num){
// 리스트 끝에 요소 삽입
lists.push_back(i);
count = count + 1;
}
// 반복자가 리스트의 끝에서 시작
for(auto iter = lists.end(); iter != lists.begin(); ++iter){
int first_ele = lists.front();
lists.pop_front();
for (int next = first_ele%10; next <= 9; next++){
int temp = first_ele*10 + next;
if (temp <= num){
lists.push_front(temp);
count++;
}
}
}
}
cout<<"count of num "<<num <<" is "<<count<<endl;
}
int main(){
count(1);
count(9);
count(7);
count(0);
count(12);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻습니다.
count of num 1 is 1 count of num 9 is 9 count of num 7 is 7 count of num 0 is 0 count of num 12 is 11