문제 출처 - Programmers
문제는 여기
[풀이]
1. DFS 탐색을 한다.
2. DFS의 종료 조건은 아래와 같다.
2-1. 현재 탐색의 깊이가 8보다 커진다면 종료
2-2. 현재 값이 구하고자 하는 수와 같다면 최솟값을 비교 후 갱신
3. 반복문을 돌며 자릿수를 늘려간다. (2, 22, 222 이처럼 붙여서 쓸 수도 있기 때문에)
4. 3에서 구해진 값과 현재의 값을 사칙연산을 하며 DFS 탐색을 진행한다.
5. 처음 Max값을 준 min의 값이 그대로라면 8번안에 못 만드는 것이므로 -1을 아니라면 최솟값을 출력한다.
[접근]
1. DP를 사용해 각 숫자를 구하는 데 필요한 최소값을 DP 배열에 담아야겠다고 생각하였으나 생각해야 할 부분이 너무 많아지는 것 같아 DFS로 해결하였다.
[코드]
import java.util.*;
class Solution {
static int min = Integer.MAX_VALUE;
static int num;
static int n;
public int solution(int N, int number) {
num = number;
n = N;
dfs(0, 0);
// 8보다 크면 바로 리턴되므로
// 최고값인 상태
if (min == Integer.MAX_VALUE)
return -1;
return min;
}
public void dfs(int depth, int current) {
// 최소값이 8보다 크면 종료
if (depth > 8) {
return;
}
// 표현해야 하는 숫자와 현재 값이 같으면
if (num == current) {
// 현재까지의 깊이와 최소값을 비교해서 갱신
min = Math.min(depth, min);
return;
}
int temp = 0;
for (int i = 0; i < 8; i++) {
// 깊이 + 자릿수가 8보다 작아야함
if (depth + i < 8) {
// 자릿수 늘리기 (2, 22, 222, 2222 이런식으로)
temp = temp * 10 + n;
// 값을 통해 사칙연산하기
dfs(depth + i + 1, current + temp);
dfs(depth + i + 1, current - temp);
dfs(depth + i + 1, current / temp);
dfs(depth + i + 1, current * temp);
}
}
}
}
'문제 풀이 > Programmers' 카테고리의 다른 글
[프로그래머스] H-Index (JAVA) (0) | 2022.04.01 |
---|---|
[프로그래머스] 주식가격 (JAVA) (0) | 2022.03.31 |
[프로그래머스] 조이스틱 (JAVA) (0) | 2022.03.29 |
[프로그래머스] 두 정수 사이의 합 (JAVA) (0) | 2022.03.28 |
[프로그래머스] 체육복 (JAVA) (0) | 2022.03.27 |