Step-by-Step
[Java] 백준14888 - 연산자 끼워넣기 본문
https://www.acmicpc.net/problem/14888
DFS 방법을 익힐때 접했던 문제이다.
※ 포인트
- 3번째 줄에서 입력값으로 받는 사칙연산의 개수는 op로 선언된 int[] 배열에 저장
- dfs를 실행하면서 op[i] 값이 0보다 크면(사용할 수 있는 연산자가 남아있을 경우) 반영하여 재귀호출
- 이때 op[i]는 한 번 사용했으므로 1감소 시켜줌
- cnt가 n일때 (사칙연산 n-1개가 모두 할당되었을 때) 결과값의 min, max를 비교한 후 리턴
package BOJ_SS;
import java.util.*;
public class boj14888 {
static int max = Integer.MIN_VALUE, min=Integer.MAX_VALUE, n;
static int[] op = new int[4];
static ArrayList<Integer> nums;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
nums = new ArrayList<>();
for(int i=0; i<n; i++)
nums.add(sc.nextInt());
for(int i=0; i<4; i++)
op[i]=sc.nextInt();
dfs(1, nums.get(0));
System.out.println(max);
System.out.println(min);
}
public static void dfs(int cnt, int totNum) {
if(cnt == n) {
max = Math.max(max, totNum);
min = Math.min(min, totNum);
return ;
}
for(int i=0; i<4; i++) {
if(op[i]>0) {
op[i]--;
switch(i) {
case 0:
dfs(cnt+1, totNum + nums.get(cnt));break;
case 1:
dfs(cnt+1, totNum - nums.get(cnt));break;
case 2:
dfs(cnt+1, totNum * nums.get(cnt));break;
default:
dfs(cnt+1, totNum / nums.get(cnt));
}
op[i]++;
}
}
}
}
'언어 > JAVA' 카테고리의 다른 글
[Java] 백준14890 - 경사로 (0) | 2022.10.20 |
---|---|
[Java] 백준14889 - 스타트와 링크 (0) | 2022.10.19 |
[Java] 백준1926 - 그림 (1) | 2022.09.23 |
[Java] 프로그래머스 - 주차 요금 계산 (0) | 2022.09.22 |
[Java] 프로그래머스 - k진수에서 소수 개수 구하기 (0) | 2022.09.22 |
Comments