백트래킹으로 모두 탐색... -> 최소값 찾기
import java.awt.*;
import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[] num;
static int[] operator;
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
static Queue<Integer> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
num = new int[N];
operator = new int[4];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
num[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int i=0;i<4;i++){
operator[i] = Integer.parseInt(st.nextToken());
}
solve(num[0], 1);
System.out.println(max);
System.out.print(min);
}
private static void solve(int a, int idx) {
if(idx==N){
max = Math.max(a, max);
min = Math.min(a, min);
return;
}
for(int i=0;i<4;i++){
if(operator[i]>0){
operator[i]--;
switch (i){
case 0: solve(a+num[idx], idx+1);break;
case 1: solve(a-num[idx], idx+1);break;
case 2: solve(a*num[idx], idx+1);break;
case 3: solve(a/num[idx], idx+1);break;
}
operator[i]++;
}
}
}
}
오늘의 회고
- 재귀, 백트래킹을 아직 제대로 구현하지 못하는 것 같다.. 한참 헤매다가 결국 풀이 보고 풀었다
- 재귀, 백트래킹 관련 문제 유형 많이 풀어볼 것
- 내일(4/12) 학습 예정 : 알고리즘 문제 풀이 (최대한 많이)
'algorithm > 문제 풀이' 카테고리의 다른 글
99클럽 코테 스터디 13일차 TIL - 백준 15654 (N과 M (5)) (0) | 2024.04.13 |
---|---|
99클럽 코테 스터디 12일차 TIL - 프로그래머스 연속된 부분 수열의 합 (0) | 2024.04.12 |
99클럽 코테 스터디 10일차 TIL - 프로그래머스 이진 변환 반복하기 (0) | 2024.04.10 |
99클럽 코테 스터디 9일차 TIL - 백준 1697번 (숨바꼭질) (0) | 2024.04.09 |
99클럽 코테 스터디 8일차 TIL - 백준 1931 (회의실배정) (0) | 2024.04.08 |