|
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
|
class Solution {
private static int min = 9;
public static void DFS(int num, int N, int cnt, int res) {
// 최솟값 갱신
if (num == res) {
min = Math.min(cnt, min);
return;
}
int add = N;
// cnt가 8을 넘지 않을 경우만 수행
for (int i = 0; i < 8 - cnt; i++) {
DFS(num, N, cnt + i + 1, res + add);
DFS(num, N, cnt + i + 1, res * add);
DFS(num, N, cnt + i + 1, res - add);
DFS(num, N, cnt + i + 1, res / add);
// N이 나란히 있을 경우
add = add * 10 + N;
}
}
public int solution(int N, int number) {
int answer = 0;
DFS(number, N, 0, 0);
answer = min == 9 ? -1 : min;
return answer;
}
}
|
cs |
DFS로 사칙연산을 수행하였다.
이 과정에서 N을 이어붙인 값에 대해서도 연산 되도록 하였다.
문제 풀이는 성공으로 나왔지만, 26과 같은 특정 값에 대해서는 해결할 수 없다는 문제가 있다.
26을 (5*5*5+5)/5로 밖에 풀지 못한다.
하지만 5*5+5/5로 해결할 수 있기 때문에 틀린 해답이다.
다른 사람이 푼 해답을 첨부한다.
|
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
|
import java.util.HashSet;
import java.util.Set;
class Solution {
public int solution(int N, int number) {
int answer = -1;
Set<Integer>[] setArr = new Set[9];
int t = N;
for(int i = 1; i < 9; i++) {
setArr[i] = new HashSet<>();
setArr[i].add(t);
t = t * 10 + N;
}
for(int i = 1; i < 9; i++) {
for(int j = 1; j < i; j++) {
for(Integer a : setArr[j]) {
for(Integer b : setArr[i - j]) {
setArr[i].add(a + b);
setArr[i].add(a - b);
setArr[i].add(b - a);
setArr[i].add(a * b);
if(b != 0) {
setArr[i].add(a / b);
}
if(a != 0) {
setArr[i].add(b / a);
}
}
}
}
}
for(int i = 1; i < 9; i++) {
if(setArr[i].contains(number)) {
answer = i;
break;
}
}
return answer;
}
}
|
cs |
N을 i개 사용했을 때 나올 수 있는 모든 수를 setArr[i]에 저장한 것이다.
이 방법으로 풀면 오류 없이 해결할 수 있다.