Post

🧩 Baekjoon 1038 - κ°μ†Œν•˜λŠ” 수

🧩 Baekjoon 1038 - κ°μ†Œν•˜λŠ” 수

문제

음이 μ•„λ‹Œ μ •μˆ˜ X의 μžλ¦Ώμˆ˜κ°€ κ°€μž₯ 큰 μžλ¦Ώμˆ˜λΆ€ν„° μž‘μ€ μžλ¦Ώμˆ˜κΉŒμ§€ κ°μ†Œν•œλ‹€λ©΄, κ·Έ 수λ₯Ό κ°μ†Œν•˜λŠ” 수라고 ν•œλ‹€. 예λ₯Ό λ“€μ–΄, 321κ³Ό 950은 κ°μ†Œν•˜λŠ” μˆ˜μ§€λ§Œ, 322와 958은 μ•„λ‹ˆλ‹€.

N번째 κ°μ†Œν•˜λŠ” 수λ₯Ό 좜λ ₯ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

0은 0번째 κ°μ†Œν•˜λŠ” 수이고, 1은 1번째 κ°μ†Œν•˜λŠ” μˆ˜μ΄λ‹€. λ§Œμ•½ N번째 κ°μ†Œν•˜λŠ” μˆ˜κ°€ μ—†λ‹€λ©΄ -1을 좜λ ₯ν•œλ‹€.

μž…λ ₯

첫째 쀄에 N이 μ£Όμ–΄μ§„λ‹€. N은 1,000,000보닀 μž‘κ±°λ‚˜ 같은 μžμ—°μˆ˜ λ˜λŠ” 0이닀.

좜λ ₯

각 ν…ŒμŠ€νŠΈ μΌ€μ΄μŠ€μ— λŒ€ν•΄ ν•„μš”ν•œ μ΅œμ†Œμ˜ 배좔흰지렁이 마리 수λ₯Ό 좜λ ₯ν•œλ‹€.

예제

βœ… μž…λ ₯ 1

1
18

βœ… 좜λ ₯ 1

1
42

βœ… μž…λ ₯ 2

1
0

βœ… 좜λ ₯ 2

1
0

βœ… μž…λ ₯ 3

1
500000

βœ… 좜λ ₯ 3

1
-1

μž‘μ„± μ½”λ“œ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException {
		// μž…λ ₯ 처리
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		// λ³€μˆ˜ μ„ μ–Έ 및 μ΄ˆκΈ°ν™”
		long num = 0L;
		int index = 0;
		boolean maxFlag = false;
		
		// NUM 증가
		while (true) {
			boolean lowerFlag = false;
			
			// κ°μ†Œν•˜λŠ” 수의 λ§ˆμ§€λ§‰ κ°’
			if (num > 9876543210L) {
				maxFlag = true;
				break;
			}
			
			// λ¬΄ν•œλ£¨ν”„λ¬Έ λ‚΄ λ³€μˆ˜ μ„ μ–Έ 및 μ΄ˆκΈ°ν™”
			long rest;
			long temp = num;
			long digit = 1;
			long prev = -1;
			
			// κ°μ†Œν•˜λŠ” 수 μ—¬λΆ€ νŒλ³„
			while (temp > 0) {
				rest = temp % 10;
				digit *= 10;
				if (rest <= prev) {
					lowerFlag = true;
					break;
				}
				
				prev = rest;
				temp /= 10;
			}
			
			if (lowerFlag) {
				// κ°μ†Œν•˜λŠ” μˆ˜κ°€ μ•„λ‹ˆλΌλ©΄
				digit /= 10;
				num += digit;
				num -= num % digit;
			} else {
				// κ°μ†Œν•˜λŠ” 수라면
				if (index == n) {
					// N 번째 수라면
					break;
				}
				
				index++;
				num++;
			}
		}
		
		// 좜λ ₯ 처리
		if (maxFlag) {
			// NUM 값이 κ°μ†Œν•˜λŠ” 수의 λ§ˆμ§€λ§‰ 값보닀 크닀면
			System.out.println(-1);
		} else {
			// N 번째 κ°μ†Œν•˜λŠ” 수λ₯Ό μ •μƒμ μœΌλ‘œ μ°Ύμ•˜λ‹€λ©΄
			System.out.println(num);
		}
	}
}
  • Brute-force λ°©μ‹μœΌλ‘œ 문제λ₯Ό ν•΄κ²°ν–ˆλ‹€.

회고

  • Back-tracking을 μ΄μš©ν•΄μ„œ ν’€ μˆ˜λ„ μžˆμ„ 것 κ°™λ‹€.
  • 문제λ₯Ό ν’€λ©΄μ„œ 1_000_000번째 κ°μ†Œν•˜λŠ” 수λ₯Ό λͺ¨λ‘ ꡬ할 수 μžˆμ„μ§€, ꡬ할 수 μ—†λ‹€λ©΄ μ–΄λ–»κ²Œ μ΅œμ ν™”λ₯Ό ν• μ§€ 고민을 ν•΄λ³΄μ•˜λ‹€.
This post is licensed under CC BY 4.0 by the author.