c언어 1038번 감소하는 수 (백준)

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

#include <stdio.h>
//감소하는 수의 최댓값은 9876543210이다. 이는 int의 범위를 넘어가므로 long long int로 했다.
#define big 10 //10

long long int f(long long int j) //10^(j-1)을 리턴하는 함수
{
	if(j<=1) return 1;
	else if(j > 1 && j<=2) return 10;
	else if(j > 2 && j<=3) return 100;
	else if(j > 3 && j<=4) return 1000;
	else if(j > 4 && j<=5) return 10000;
	else if(j > 5 && j<=6) return 100000;
	else if(j > 6 && j<=7) return 1000000;
	else if(j > 7 && j<=8) return 10000000;
	else if(j > 8 && j<=9) return 100000000;
	else if(j > 9 && j<=10) return 1000000000;
	else if(j > 10 && j<=11) return 10000000000;
	else return 100000000000;
} 

int main(void)
{
	int n = 0;
	scanf("%d", &n); //몇 번째?
    
    if(n==0) { //n = 0 일 경우 바로 0 출력 후 종료
       printf("0");
       return 0;
    }
	
	long long int i = 0; //index 변수
	long long int j = 0; //index 변수
	long long int before = 0; //지금 비교하려는 수 보다 한 자릿수 위의 숫자
	long long int before_a = 0; //비교 후 가장 큰 자릿수를 제거 한 값을 담을 변수
	long long int count = 0; //감소하는 수 개수
	for(i = 1; i<=9876543210; ) //9876543210 : 가장 큰 감소하는 수
	{
		long long int b = i; //i의 자릿수를 알기위해 사용하는 변수
		long long int tmp = 0; //i의 자릿수를 담을 변수
		for(b = i; b>0; b=b/10) tmp++; //자릿수 구하기
	
		before = big; //입력받은 수의 가장 큰 자리는 비교할 이전 자리의 수가 없으므로, 이전자리에 10이 있다고 하고 비교한다.
		before_a = 0;
		
		long long int count_j = 0; //for(j=tmp; j>1;j--)을 몇 번 돌았는지를 나타내는 변수
		for(j=tmp; j>=1; j--)
		{
			long long int a = i; //비교 할 때 i을 건들 수는 없으니 a라는 변수에 i을 대입
            //특정 자리수의 수 구하기
			if(count_j != 0) a = before_a / f(j); //둘째자리 이후 자리의 수 얻기
			else a = (a-before_a) /f(j); //맨 처음자리수 얻기
			
			if(before <= a) { //만약 감소하는 수가 아니라면 i을 일정한 값으로 증가, (i을 1씩 증가시켜 비교하기엔 시간이 너무 많이 걸린다)
				i = (i-(a)*f(j)) + f(j+1); //ex) 98800은 감소하는 수가 아님 -> i = (98800-(8)*f(3)) + f(4); -> i = 98000 + 1000 = 99000
				break; //for(j..) 탈출
			}
			before = a; //이전 자리수의 값을 담는 변수에 비교가 끝난 자릿수의 값을 대입
            
            //두자리수 이상의 수에서, 가장 큰 자리수의 수를 제거 //ex (a는 비교하는 수) a = 632 -> 32 - > 2 이것을 위해서 만들어 놓은 코드
			if(count_j != 0) before_a = before_a - a*f(j); //그 다음의 수 제거
			else before_a = i - a * f(j);//가장 큰 자리수의 수 제거
			
			count_j++; //for(j~)을 몇번 반복 하고 있는지를 알기 위한 장치
		}
		if(j==0) { //j가 0이라는 뜻은 모든 각각 자리의 수가 이전의 자리의 수보다 작다는 것을 의미
			count++; //그러므로 감소하는 수 의 개수를 증가
            if(count == n) { //만약 감소하는 수의 개수와 n이 같으면 그때의 감소하는수(i)을 출력 후 종료
			    printf("%lld", i);
			    return 0;
		    }
			i++; //1씩 올려서 그 다음수도 감소하는 수인지를 확인해본다.
		}
	}
	//위의 for(i~)을 다 돌았으나, 종료되지 않고 여기까지 왔다는 것은 n > count을 의미 즉 구하고자 하는 n번째의 수가 없음을 의미한다.
	printf("-1");
}

 

풀이

 

1) 감소하는 수

0 1 2 3 4 5 6 7 8 9 10 20 21 ... 210 ... 987654....... 9876543210 까지 존재한다.

 

2) 감소하는 지 안 하는지를 알 수 있는 방법

비교하고 싶은 수 : i

i 대신 비교될 수 : a

비교 후 한 자리수가 없어진 수 : before_a

이전의 자릿수 의 값 :before

 

ex) i = 87439

a = 87439

a = 87439 / 10000(자릿수로 나눔) = 8

 

before = 10, a = 8 이므로 감소

 

before = 8

before_a = i - a * f(j) = 87439 - 8 * 10000 = 7439

 

a = before_a  / f(j) = 7439 / 1000;

....

이런 식으로 자릿수 비교를 했다.

 

3) 감소하는 수가 아닐 경우

before <= a 인 경우가 감소하는 수가 아니게 된다.

i을 1씩 증가시켜서 비교해도 되긴 하나 수가 거의 10억까지 가야 되므로, 더욱 크게 증가시켜야 한다.

ex) i = 87322 -> 87330 ->  87400 -> 87410 ->  87411 -> 87420... 

1의 자리에서 감소하지 않게되면 1의 자리의 수를 0으로 만든 뒤 10을 더해준다.

100의 자리에서 감소하지 않게되면 100의 자리까지의 수를 다 0으로 만든 뒤 1000을 더해준다.

 

이걸 코드로 만든 것이     i = (i-(a)*f(j)) + f(j+1);이다.

 

4) n개의 감소하는 수를 찾았으면 그때의 i을 출력

 n = 0은 0으로

n개의 감소하는 수가 없으면 -1을 출력하면 된다.