[백준] 14888번 / Java, Python
Baekjoon Online Judge
algorithm practice
단계별 문제풀기
13. 백트래킹
모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.
모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다.
Java / Python
7. 연산자 끼워넣기
삼성 SW 역량 테스트 기출 문제 1
- Java
import java.util.Scanner;
public class Main {
public static int MAX = Integer.MIN_VALUE; // 최댓값
public static int MIN = Integer.MAX_VALUE; // 최솟값
public static int[] oper = new int[4]; // 연산자 개수
public static int[] nums; // 숫자
public static int N; // 숫자 개수
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = sc.nextInt();
}
for (int i = 0; i < 4; i++) {
oper[i] = sc.nextInt();
}
dfs(nums[0], 1);
sc.close();
System.out.println(MAX);
System.out.println(MIN);
}
public static void dfs(int num, int idx) {
if (idx == N) {
MAX = Math.max(MAX, num);
MIN = Math.min(MIN, num);
return;
}
for (int i = 0; i < 4; i++) {
if (oper[i] > 0) {
oper[i]--;
switch (i) {
case 0: dfs(num + nums[idx], idx + 1); break;
case 1: dfs(num - nums[idx], idx + 1); break;
case 2: dfs(num * nums[idx], idx + 1); break;
case 3: dfs(num / nums[idx], idx + 1); break;
}
oper[i]++;
}
}
}
}
- Python
import sys
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
add, sub, mul, div = map(int, sys.stdin.readline().split())
min_num, max_num = 1e9, -1e9
def dfs(i, res, add, sub, mul, div):
global max_num, min_num
if i == N:
max_num = max(res, max_num)
min_num = min(res, min_num)
return
else:
if add:
dfs(i+1, res+nums[i], add-1, sub, mul, div)
if sub:
dfs(i+1, res-nums[i], add, sub-1, mul, div)
if mul:
dfs(i+1, res*nums[i], add, sub, mul-1, div)
if div:
dfs(i+1, int(res/nums[i]), add, sub, mul, div-1)
dfs(1, nums[0], add, sub, mul, div)
print(max_num)
print(min_num)
Author And Source
이 문제에 관하여([백준] 14888번 / Java, Python), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jini_eun/백준-14888번-Java-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)