https://school.programmers.co.kr/learn/courses/30/lessons/42895
코딩테스트 연습 > 동적계획법(Dynamic Programming) > N으로 표현
난이도: LEVEL3
알고리즘 유형: 완전 탐색?
풀이 설명
문제 카테고리는 동적계획법 dp 이지만 나는 완전 탐색으로 풀었다.
어떻게 보면 이전 depth의 경우의 수를 기록하니 dp - 메모제이션 방식인 것 같기도 하다.
n을 1개 사용 ~ n을 8개 사용까지 모든 경우의 수를 다 구한다.
경우의 수 저장은 Set에 했다. 중복된 수가 있다.
static ArrayList<Set<Integer>> list = new ArrayList<>();
index i의 의미: n을 i개 사용
depth를 1씩 늘리면서 Set에 찾는 값이 있는지 확인한다.
Set에 값을 넣는 방식
ex)
n = 4
1, 3 / 2, 2 / 2, 2 / 3, 1 / 4
더하기 곱하기는 순서와 상관없지만 나누기 빼기는 순서에 따라 달라진다.
4의 의미는 순수하게 사칙연산 없이 n만 사용
1, 3 같은 경우는 n을 1개 사용과 n을 3개 사용의 사칙연산이다.
정답 코드
import java.util.*;
class Solution {
static ArrayList<Set<Integer>> list = new ArrayList<>();
static int n;
static int target;
static int answer = 9;
public int solution(int N, int number) {
n = N;
target = number;
init();
bt(1);
return answer == 9 ? -1 : answer;
}
public static void bt(int depth){
if(list.get(depth).contains(target)){
answer = depth;
return;
}
if(depth == 8) return;
int next = depth + 1;
Set<Integer> nextSet = list.get(next);
for(int i = 1; i <= depth; i++){
Set<Integer> set1 = list.get(i);
Set<Integer> set2 = list.get(next - i);
for(int cur1 : set1){
for(int cur2: set2){
nextSet.add(cur1 + cur2);
nextSet.add(cur1 - cur2);
nextSet.add(cur1 * cur2);
if(cur2 == 0) continue;
nextSet.add(cur1 / cur2);
}
}
}
bt(next);
}
public static void init(){
StringBuilder sb = new StringBuilder();
list.add(new HashSet<>()); // 0 index
for(int i = 1; i <= 8; i++){
sb.append(n);
list.add(new HashSet<>());
list.get(i).add(Integer.parseInt(sb.toString()));
}
}
}
'Algorithm > Programmers Java' 카테고리의 다른 글
[JAVA] 프로그래머스 LEVEL3 파괴되지 않은 건물 (0) | 2024.11.05 |
---|---|
[JAVA] 프로그래머스 LEVEL3 풍선 터트리기 (1) | 2024.11.03 |
[JAVA] 프로그래머스 LEVEL3 기지국 설치 (0) | 2024.10.30 |
[JAVA] 프로그래머스 LEVEL3 정수 삼각형 (1) | 2024.10.30 |
[JAVA] 프로그래머스 LEVEL3 징검다리 건너기 (2) | 2024.10.28 |