반응형
백준 감소하는 수(줄어드는 수)
https://www.acmicpc.net/problem/1174
https://www.acmicpc.net/problem/1038
접근 방식
최초엔 n까지 범위의 수를 생각했는데, 잘못 생각한 것이였고, 앞자리부터 점점 감소하는 수의 모든 경우의 수 중 몇번째인지 n으로 입력받아 찾는 문제
구현 방법
- 감소하는 수에 대해 모든 조합을 찾은 후 정렬해 수행
- 이 때 최대 수의 범위까지 1씩 더해가며 찾는 것이 아닌, 값이 들어갈 수 있는 범위에 대해서만 찾기
⇒
- 9876543210 까지가 최대 수
- 재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
- 기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
- 재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
- for문이 다 돌면 재귀호출 시행
풀이
package Baekjoon.gold;
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
public class p1174 {
static Stack<Long> st = new Stack<>();
static ArrayList<Long> al = new ArrayList<>();
static int count = 0;
static int n;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
/*
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, 85, 86, 87 | 90, 91, 92, 93, 94, 95, 96, 97, 98 |
210 |320, 321, 310 | 410, 420, 421, 430, 431, 432
*/
//9 -> 8 7 6 5 4 3 2 1 0
//8 -> 7 6 5 4 3 2 1 0
//7 -> 6 5 4 3 2 1 0
//6 -> 5 4 3 2 1 0
//5 -> 4 3 2 1 0
//4 -> 3 2 1 0
//3 -> 2 1 0
//2 -> 1 0
//1 -> 0
// 10 20 21 30 31 32
//9876543210 까지가 최대 수
//재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
//기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
//재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
//for문이 다 돌면 재귀호출 시행
if(n <= 10){
System.out.println(n-1);
return;
}
recur(10);
List<Long> list = al.stream().sorted().collect(Collectors.toList());
long result = -1;
if(list.size() >= n){
result = list.get(n-1);
}
System.out.println(result);
}
private static void recur(long nowNum){
for(long i = 0; i < nowNum; i++){
count++;
st.push(i);
st.forEach(sb::append);
al.add(Long.valueOf(sb.toString()));
sb.setLength(0);
recur(i);
st.pop();
}
}
}
후기
최초에 문제를 잘못 읽었고, 이후엔 전체 탐색을 효율적으로 하기위한 노력(가지치기)을 하는 데 시간을 많이 썼음
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 백준 25916 싫은데요 자바로 풀어 본 짧은 글 (1) | 2023.12.21 |
|---|---|
| 백준 16987 계란으로 계란치기 자바로 풀어 본 짧은 글 (0) | 2023.12.13 |
| 백준 2866 문자열 잘라내기 자바로 풀어 본 짧은 글 (2) | 2023.12.08 |
| 백준 2805 나무 자르기 자바로 풀어 본 짧은 글 (2) | 2023.12.03 |
| 백준 16401 과자 나눠주기 자바로 풀어 본 짧은 글 (0) | 2023.12.02 |
