반응형
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
문제 분석
처음의 연산할 숫자의 개수가 주어지고, 둘째 줄에는 연산할 수, 셋째 줄에는 연산자의 개수가 주어진다.
예를 들어 입출력 2를 보면,
3
3 4 5
1 0 1 0
연산자는 + , x 각 1개씩 사용 가능하다.
모든 경우의 연산을 보면,
3 + 4 x 5 = 35
3 x 4 + 5 = 17
결과가 35, 17인 두가지 경우가 나온다.
먼저 재귀 함수 부분 코드를 살펴보자.
static void dfs(int depth, int sum) {
/* 종료 조건 */
if (depth == N) {
if (MAX < sum) MAX = sum; // 왜 if-if 로 구현 했는가?
if (MIN > sum) MIN = sum; // 만약, 결과 값이 2, 3, 4 순으로 온다면 if-else로 구현했다면, MAX 값만 변경 되면서 MIN값이 제대로 안들어 갔을 것이다.
return;
}
for (int i = 0; i < N - 1; i++) {
int cur = numbers[depth]; // 함수의 깊이에 따라 숫자를 뽑는다.
if (!isUsed[i]) { // 연산자를 사용한 적이 있는지 확인
isUsed[i] = true; // 만약 없다면, 해당 연산자를 사용했다고 체크!
int result = calc(sum, cur, operators[i]); // 계산 식으로 이동.
dfs(depth + 1, result); // 재귀 호출 부분(깊이+1, 계산한 결과 값(result)를 전달)
isUsed[i] = false; // 재귀 호출이 모두 끝났다고 생각하고, 다시 비 방문 처리.
}
}
}
재귀의 깊이(depth)로 연산할 숫자의 배열 인덱스로 사용하고, 재귀 함수 안에 for문으로 연산자 배열을 체크하면서, 계산을 해서 다시 재귀 호출을 하면서 파라미터로 (깊이, 연산한 결과 값) 를 넘겨준다.
연산하는 calc 함수 구현
static int calc(int sum, int num, String oper) {
switch (oper) {
case "+": sum += num; break;
case "-": sum -= num; break;
case "*": sum *= num; break;
case "/": sum /= num; break;
}
return sum;
}
switch 문으로 파라미터로 넘어온 연산자(oper) 문자열에 따라 연산 결과를 리턴 한다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int MAX = Integer.MIN_VALUE; // 최대값
static int MIN = Integer.MAX_VALUE; // 최소값
static String[] operators; // 연산자 배열
static boolean[] isUsed; // 연산자 사용 여부 체크
static int[] numbers; // 계산할 숫자 배열
static int N; // 숫자 개수
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(bf.readLine());
numbers = new int[N];
operators = new String[N-1];
isUsed = new boolean[N];
/* numbers 받기 */
st = new StringTokenizer(bf.readLine());
for (int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
/* operators 받기 */
int index = 0;
String oper = "+-*/";
st = new StringTokenizer(bf.readLine());
for (int i = 0; i < 4; i++) {
int n = Integer.parseInt(st.nextToken());
if (n > 0) {
String op = oper.substring(i, i + 1);
while (n-- > 0) {
operators[index++] = op;
}
}
}
dfs(1, numbers[0]);
System.out.println(MAX);
System.out.println(MIN);
}
static void dfs(int depth, int sum) {
/* 종료 조건 */
if (depth == N) {
if (MAX < sum) MAX = sum;
if (MIN > sum) MIN = sum;
return;
}
for (int i = 0; i < N - 1; i++) {
int cur = numbers[depth];
if (!isUsed[i]) {
isUsed[i] = true;
int result = calc(sum, cur, operators[i]);
dfs(depth + 1, result);
isUsed[i] = false;
}
}
}
static int calc(int sum, int num, String oper) {
switch (oper) {
case "+": sum += num; break;
case "-": sum -= num; break;
case "*": sum *= num; break;
case "/": sum /= num; break;
}
return sum;
}
}
반응형