[백준] 14888번 연산자 끼워넣기 JAVA (자바) 풀이
문제 14888번
: N개의 수열 (A1, ... , AN) 주어진다
수 사이에 끼워넣을 수 있는 N-1개의 연산자 (+ 덧셈, - 뺄셈, × 곱셈, ÷ 나눗셈) 주어진다
숫자 순서 바꿀 수 X, 연산자 순서 바꿀 수 O
: 우선순위 무시하고 앞에서부터 계산
나눗셈은 몫만 구하고, 음수를 양수로 나눌 때에는 숫자끼리만 나누고 몫에 -만 붙여준다 (=음수처리)
: 결과식 최대인 것과 최소인 것을 구해라
[입력]
: 첫 줄에 수열 개수 N
: 둘째 줄 N개의 수열
: 연산자 개수 ( +, -, ×, ÷ 순서 )
[출력]
: 식 최댓값 첫째줄에, 식 최솟값 둘째줄에 출력
[알고리즘]
- 모든 경우를 분석해야 하는구나 = 완전 탐색 = 브루트 포스
- 연산자의 조합을 이용해야 한다 = 순열
- 순열을 쉽게 구하기 위해서는 백트래킹
→ 이 문제는 백트래킹 문제로 풀어야 한다
→ 재귀를 이용하고 있고 가지치기를 하지 않기 때문에 dfs로 풀었다고 봐도 무방하다
- 브루트 포스 (완전탐색) = 모든 가능한 경우를 전부 탐
- 백트래킹 = 탐색을 진행하고 조건에 맞지 않는 부분을 제외하면서 탐색
- DFS = 트리를 완전 탐색하는 한가지 방법, 모든 경로 탐색
[설명 예시]
<백트래킹 코드 과정>
[1] for문 4번 돌기
이는 각 수열마다 연산자를 모두 돌리기 위함이다
(예) 수열에서 1과 2 사이에는 연산자 4가지 종류를 모두 넣는다
[2] 연산 배열이 0보다 클 때 if문 실행
1. 연산 배열 하나 줄이기 (연산자를 사용했다는 표시)
2. switch ~ case 문을 통해 해당 연산자가 무엇인지 파악하고
연산자를 넣어 계산한 값과 index(계산 횟수)를 다음 백트래킹에 대입
3. 연산 배열 다시 ++ (여러 경우의 수 계산을 위해 다시 사용하려고 ++)
이때 중요한 것은 2번 과정에서 하위 백트래킹과정까지 모두 마친 뒤에 실행한다
[3] index = N 일 경우 max와 min을 갱신해서 여러 경우의 수를 비교한다
(예시) for문에서 i = 0인 경우
[코드]
import java.util.*;
import java.io.*;
public class Main{
static int N;
static int arr[];
static int cal[] = new int[4];
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
arr = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++){
cal[j] = Integer.parseInt(st.nextToken());
}
Back(arr[0],1);
System.out.println(max);
System.out.println(min);
}
public static void Back(int step, int index){
if(index == N){
max = Math.max(max,step);
min = Math.min(min,step);
return;
}
for(int i=0; i<4; i++){
if(cal[i]>0){
cal[i]--;
switch(i){
case 0:
Back(step + arr[index], index+1);
break;
case 1:
Back(step - arr[index], index+1);
break;
case 2:
Back(step * arr[index], index+1);
break;
case 3:
Back(step / arr[index], index+1);
break;
}
cal[i]++;
}
}
}
}
[해설]
: static int N; 수열 개수
static int arr[]; 수열 배열
static int cal[] = new int[4]; 연산자 배열
static int max = Integer.MIN_VALUE; 정수 최대값
static int min = Integer.MAX_VALUE; 정수 최소값
: N = Integer.parseInt(br.readLine()); 첫째줄 입력
arr = new int[N]; arr배열 크기 지정
: st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++){ 두번째 줄 입력 arr배열에 넣기
arr[i] = Integer.parseInt(st.nextToken());
}
: st = new StringTokenizer(br.readLine());
for(int j=0;j<4;j++){ 세번째 줄 입력 cal배열에 넣기
cal[j] = Integer.parseInt(st.nextToken());
}
: Back(arr[0],1); 백트래킹 실행
: System.out.println(max); 출력1
System.out.println(min); 출력2
: public static void Back(int step, int index){ 백트래킹 실행
if(index == N){ 연산횟수가 N만큼 돌아가면 끝
max = Math.max(max,step); 마지막 N번째 연산 결과인 step과 max 값 비교 후 갱신
min = Math.min(min,step); 마지막 N번째 연산 결과인 step과 min 값 비교 후 갱신
return;
}
for(int i=0; i<4; i++){ 연산자 4종류라서 각 수열마다 모두 돌려보기
if(cal[i]>0){ 연산 배열에 값이 있을 경우 해당 연산자를 통해 아래 함수들 수행
cal[i]--; 해당 연산자 하나 사용했다는 표시
switch(i){ 해당 연산자가 무엇인지 파악
case 0: 연산자 + 일 경우
Back(step + arr[index], index+1); 연산한 값으로 다시 재귀, index++
break;
case 1: 연산자 - 일 경우
Back(step - arr[index], index+1); 연산한 값으로 다시 재귀, index++
break;
case 2: 연산자 × 일 경우
Back(step * arr[index], index+1); 연산한 값으로 다시 재귀, index++
break;
case 3: 연산자 ÷ 일 경우
Back(step / arr[index], index+1); 연산한 값으로 다시 재귀, index++
break;
}
cal[i]++; 백트래킹 과정 모두 끝났을 경우 다른 경우의 수 계산을 위해 연산 배열 ++
}
}
}
[시간 복잡도]
| 시간 복잡도 | 최대 N | 연산 횟수 한계 |
| O(N) | 1억 | 1억번 |
| O(NlogN) | 5백만 | |
| O(N^2) | 1만 | |
| O(N!) | 11 |
수열의 최대 개수는 11 / 연산자 최대 개수는 10
연산자는 한번 쓰일 때 4가지의 경우를 갖는다
즉 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 × 4 = 4^10 이므로 2억번 보다 적어 수행 가능하다
시간복잡도는 O(4ⁿ) 이다
이제 풀어보러 갈께요 :)
https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱
www.acmicpc.net
* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *