G1174. 줄어드는 수

문제

제출 코드

• 사용 알고리즘 : 백트래킹

문제를 살짝 지저분하게 풀은 것 같다.

N번째까지 줄어드는 수를 직접 구해야한다고 생각해서, 1의자리 수부터 자리수를 늘려가며 작은 수 순서대로 줄어드는 수를 계산해서, N번째에 도달할 경우 그 수를 반환하도록 go함수를 작성했다.

문제를 한번에 풀지 못했던 이유는, N번째로 작은 수를 구할 수 없는 경우를 생각하지 못했기 때문이다.

처음엔 정수의 범위를 초과하는 것을 얘기하는 줄 알고 Integer.MAX_VALUE를 초과하는 경우로 생각했지만 이게 아니었다.

“줄어드는 수”이기 때문에, 숫자를 구성하는 각 자리수들은 중복값이 들어갈 수 없으므로 2^10 = 1024에서 0~9 중 아무 숫자도 선택하지 않는 경우를 뺀 1023가지밖에 만들수 없었더라.

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class G1174_decreasigNumber {
	static int N, cnt=1;

	static long go(int n, int idx, double num) {
		if(idx==0) {
			if(++cnt==N) {
				return (long)num;
			}
			else return -11;
		}

		for(int i=0; i<n; i++) {
			long res = go(i, idx-1, num+i*Math.pow(10, idx-1));
			if(res!=-11) {
				return res;
			}
		}

		return -11;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		if(N==1) {
			System.out.println(0);
			return;
		}
		int idx=0;
		while(cnt!=N) {
			for(int i=1; i<=9; i++) {
				long res = go(i, idx, i*Math.pow(10, idx));
				if(res != -11) {
					System.out.println(res);
					return;
				}
			}
			if(++idx>1023) {
				System.out.println(-1);
				return;
			}
		}

	}

}