문제
https://www.acmicpc.net/problem/1174
풀이
문제는 너무 단순한데 보자마자 쉽게 어떻게 풀지 떠오르지가 않았습니다.
구래서, 일단 제일 작은수부터 나열해보았습니다.
0
1
2
0
1
2
3
4
5
6
7
8
9
10
20
21
30
31
32
40
41
42
43
50
51
52
53
54
60
61
62
63
64
65
70
71
72
73
74
75
76
80
81
82
83
84
.,
97
98
(세자리)
210
…
(네자리)
3 2 1 0
(다섯자리)
4 3 2 1 0
(여섯자리)
5 4 3 2 1 0
…
(열자리)
9 8 7 6 5 4 3 2 1 0
(열한자리)
없음..
그러다보니 이렇게 열한자리는 줄어드는 수가 없어야 한다는걸 알게되었고 어떠한 특징을 알게되었습니다!
그 특징이 뭐냐면 2자리수를 예로들어보면
98 97 96 .... 87 86 85 ... 76 75 74 .. 를 거꾸로 하여 숫자가 나열된다는 것이죠!
이걸보고 바로 백트래킹으로 recursive함수를 이용해야겠단 생각이들면 굿!
그리고 recursive결과 데이터들을 결국 거꾸로 뒤집어야해서
스택을 이용했습니다!(뒤집기 위해서)
스택에 넣고, 다 넣으면 pop을해서 거꾸로 맵에 저장했습니다.!(저는 줄어드는 수를 맵을 통해서 저장했습니다. 맵으로 찾고자 하는 줄어드는 수의 인덱스를 통해 쉽게 데이터에 접근할수 있기 때문이죠!)
그리구 하나더! 저는 각 자리수마다 접근했습니다. 어차피 11자리 이상에는 줄어드는 수가 없으닌까 1자리부터 10자리까지 존재할수있는 줄어드는 수를 순서대로 맵에 저장하는 형식으로요!
그래서 결국 마지막에 출력하는 형식에는 맵의 사이즈보다 큰 입력이 N으로 들어오면 안되겠죠!@!@!@
코드
package training.backtracking;
//N번째로 작은 줄어드는 수..
//한자리수부터 열자리수 까지밖에 줄어드는수없음
//열한자리수부터는 줄어드는수가 없다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class Main1174 {
static Map<Integer, Long> map = new HashMap<>();
static int N;
static int[] result;
static Stack<Long> stack;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
for(int i = 1; i <= 10; i++){
map.put(i, (long)(i - 1));
}
int start = 11;
for(int i = 2; i <= 10; i++){
//i : 자리수
result = new int[i];
stack = new Stack<>();
recursive(i, 0, 9);
while(!stack.isEmpty())
map.put(start++, stack.pop());
}
if(N > map.size()){
System.out.println(-1);
}else{
System.out.println(map.get(N));
}
}
static void recursive(int M, int m, int start){
if(m == M){
StringBuilder sb = new StringBuilder();
for (int i : result) {
sb.append(i);
}
stack.push(Long.parseLong(sb.toString()));
return;
}
for(int i = start; i >= 0; i--){
result[m] = i;
recursive(M, m + 1, i - 1);
}
}
}
'algorithm' 카테고리의 다른 글
백준 3980(JAVA) (0) | 2021.11.01 |
---|---|
백준 2661(JAVA) (0) | 2021.10.31 |
백준 16987(JAVA) (0) | 2021.10.12 |
백준 10971(JAVA) (0) | 2021.10.11 |
백준 15649(JAVA) (0) | 2021.10.04 |