첫 시도
- N은 8까지, number는 2^5 * 10^4이므로 O(number^2)은 불가능
- 1은 N/N일 수 밖에 없으므로 dp[1] = 2 일 수 밖에 없다. -> 이것을 이용해서 1부터 32000까지 최소값을 구해보려고 시도 -> 이렇게는 못 구함 -> 실패
해결
- 1부터 32000까지 N 개수의 최소값을 구하는게 아니라 N의 갯수를 기준으로 결과값을 Set에 저장하는 방식으로 구현
- N이 5라고 했을 때 계산법에 5가 1개 있는 Set에는 5 1개밖에 없다
- 5가 2개 있는 Set에는 5 + 5 = 10, 5 - 5 = 0, 5 * 5 = 25, 5 / 5 = 1, 55로 총 5개가 들어가게 된다.
- 5가 3개 있는 Set에는 5 + (5가 2개인 값) = ? 로 설명할 수 있게 되어 dp를 사용할 수 있다.
- N이 8을 초과하면 -1을 반환해줘야 하므로 N은 8까지만 구한다.
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
import java.util.*;
class Solution {
public int solution(int N, int number) {
int answer = 0;
Set<Integer>[] arr = new HashSet[9];
int n = 0;
for (int i = 1; i < 9; i++) {
n = (n * 10) + N;
arr[i] = new HashSet<>();
arr[i].add(n);
}
for (int i = 1; i <= 8; i++) {
for (int j = 1; j < i; j++) {
for (Integer a : arr[j]) {
for (Integer b : arr[i - j]) {
arr[i].add(a + b);
arr[i].add(a - b);
arr[i].add(a * b);
if (b != 0 && a != 0) {
arr[i].add(a / b);
arr[i].add(b / a);
}
}
}
}
if (arr[i].contains(number)) {
answer = i;
return answer;
}
}
return -1;
}
}