π§© 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.