<Algorithm> 131. 최대상금(SWExpert)
by BFine반응형
최대상금(SWExpert)
- DFS 문제
- 난이도는 낮은데 정답률이 낮아서 풀어본 문제, 난이도에 비해 생각하는 과정이 조금 어려운 부분이 있었다.
- 처음에는 당연히 시간도 20초라서 완전탐색인줄 알아서 상단히 난해한 부분이 있었다. 그 후에 DFS라는 힌트를 보고 풀었다.
- 또 DFS로 완전탐색하니까 시간초과가 발생했다. 앞자리가 클때만 바꿔주는 것을 추가했더니 통과가 되었다.
|
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
|
import java.util.Scanner;
public class Solution {
static int max;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
/******************************
* DFS 탐색을 이용하여 자리를 바꿨을떄
* 숫자가 커지는 모든 경우의 탐색하여
* 최댓값을 구한다.
*******************************/
for(int t = 1; t <= T; t++ ) {
int num = sc.nextInt();
int n = sc.nextInt();
int len = String.valueOf(num).length();
max = Integer.MIN_VALUE;
dfs(num, n, 0, 0,len);
System.out.println("#"+t+" "+max);
}
}
public static void dfs(int num, int n, int idx,int cnt,int len) {
if(n == cnt) {
max = Math.max(max, num);
return;
}
for(int i = idx; i < len; i++) { // 삼각탐색
for(int j = i; j < len ; j++) {
if(i == j) continue;
int a = String.valueOf(num).charAt(i)-'0';
int b = String.valueOf(num).charAt(j)-'0';
if(b >= a) {
int num_swap = swap(num, i, j);
dfs(num_swap, n, i, cnt+1, len);
}
}
}
}
public static int swap(int num, int start, int idx) {
char[] chrarr = String.valueOf(num).toCharArray();
char temp = chrarr[start];
chrarr[start] = chrarr[idx];
chrarr[idx] = temp;
String str = new String(chrarr, 0, chrarr.length);
return Integer.parseInt(str);
}
}
|
|
|
|
|
|
|
cs |
참고 & 출처
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 133. 동철이의 일분배(SWExpert) (0) | 2019.03.15 |
|---|---|
| <Algorithm> 132. 동아리실 관리하기(SWExpert) (0) | 2019.03.14 |
| <Algorithm> 130. 하나로(SWExpert) (0) | 2019.03.09 |
| <Algorithm> 129. 장훈이의 높은 선반(SWExpert) (0) | 2019.03.08 |
| <Algorithm> 128. 러시아 국기 같은 깃발(SWExpert) (0) | 2019.03.03 |
블로그의 정보
57개월 BackEnd
BFine