26. 14888번 연산자끼워넣기
고려해야할점은
1. 주어진 수의 순서를 바꾸면 안된다는것
2. 연산자 우선순위를 무시한다는것
3. 음수를 양수로 나눌때는 양수로 바꾸어 몫을 취하고 그 몫을 음수로 바꾸어준다는 것
ex) -8 / 4 => 8 / 4 => 2 => -2
+ 식의 결과는 정수의 범위를 벗어나지않는다 ( +- 10억 )
문제에서 주어지는 것 N개의 수 N-1개의 연산자
구해야 하는것 식의 최대값 최소값
피연자인 숫자는 위치가 고정되고 연산자의 위치만 바꿀수 있다
입력한 수들과 연산자들의 개수를 입력 해주면 모든 경우의 수를 탐색한뒤 가장 큰값과 가장 작은 값을 찾는 문제
DFS(깊이 우선 탐색)기법을 이용하여 전체 경우의 수를 탐색한다.
int[] number; // 숫자
int[] operator; // 연산자 개수
public static void dfs(int num, int idx) {
for (int i = 0; i < 4; i++) { //연산자 개수 4개 배열 0,1,2,3
// 연산자의 개수가 하나라도 남아있으면 if문으로 들어온다
if (operator[i] > 0) {
// 사용되는 연산자 1감소
operator[i]--;
//연산자 계산식
switch (i) {
case 0 : dfs(num + number[idx], idx + 1); break;
case 1 : dfs(num - number[idx], idx + 1); break;
case 2 : dfs(num * number[idx], idx + 1); break;
case 3 : dfs(num / number[idx], idx + 1); break;
}
// 백트래킹 연산자 개수를 돌려놓음
operator[i]++;
}
}
}
여러 연산자 즉, ( 1 0 1 0 ) 과 같은 형태로 입력을 받았을 시에
앞의 연산자부터 차례대로 1씩 감소하며 연산해준다.
예를들어 숫자는 7 5 4 3
연산자는 1 1 0 1 이라고 가정하고 위의 DFS를 돌려본다면
| 남은수 | 연산자들 | 해당연산자 | 값 | 깊이 |
| (7,5),4,3 | 1,1,0,1 => 0,1,0,1 |
+ | 7+5 = 12 |
1+1 = 2 |
| (12,4),3 | 0,1,0,1 => 0,0,0,1 |
- | 12-4 = 8 |
2+1 = 3 |
| 8,3 | 0,0,0,1 => 0,0,0,0 |
/ | 8/3 = 2.6666... |
3+1 = 4 |
| operator[0]번째 부터 첫번째 탐색 완료 이후 operator[1]번째 부터 두번째 탐색 시작 |
||||
| (7,5),4,3 | 1,1,0,1 => 1,0,0,1 |
- | 7-5 = 2 |
1+1 = 2 |
| (2,4),3 | 1,0,0,1 => 0,0,0,1 |
+ | 2+4 = 6 |
2+1 = 3 |
| 3,3 | 0,0,0,1 => 0,0,0,0 |
/ | 3/3 = 1 |
3+1 = 4 |
| operator[1]번째 부터 두번째 탐색 완료 이후 operator[2]번째 부터 세번째 탐색 시작 그러나 operator[2] = 0 이기에 바로 이어서 operator[3]번째 부터 탐색 시작 |
||||
| (7,5),4,3 | 1,1,0,1 => 1,1,0,0 |
/ | 7/5 = 1.4 |
1+1 = 2 |
| (1.4,4),3 | 1,1,0,0 => 0,1,0,0 |
+ | 1.4+4 = 5.4 |
2+1 = 3 |
| 5.4,3 | 0,1,0,0 => 0,0,0,0 |
- | 5.4-3 = 2.4 |
3+1 = 4 |
| 모든 탐색 완료 | ||||
위 테이블의 예시대로한다면 처음 (7,5,4,3)수와 (1,1,0,1)연산자들을 이용해서
첫번째
깊이 가 N이 될때까지 즉, idx가 4가 될때까지 돌린다. 이 말의 뜻은 모든 연산자가 사용되어 값이 나왔을때
그 값이 기존 num과 비교하여 Max 값과 Min값에 저장해 두는것이다.
두번째
op[0] 즉 +연산자부터 차곡차곡 실행한다
op[0]은 1 , op[0]-- 로 계산했다는 표시로 감소시켜준다
이경우에는 0이 되었다.
이후 식을 진행하면 num(7)과 number(idx(1)=5)를 case 0 = + 처리해주고 idx 에 +1 해준다
값은 12, idx는 2 그리고 다시 재귀한다 dfs(12,2)
다시 for문을 시작
op[0]부터 찾아준다, 그러나 지금은 1101 에서 +를 소비한 0101 상태이기에 op[1]로 다시시작
num(12)와 number(idx(2)=4)를 case 1 = - 처리해주고 idx +1 해준다
값은 8 , idx는 3 그리고 다시 재귀한다 dfs(8,3)
다시 for문을 시작
op[0]부터 다시찾아준다, 그러나 지금은 1101 에서 + 와 - 를 소비한 0001 상태이기에 op[1],op[2] 를 넘긴 op[3] 시작
num(8)과 number(idx(3)=3)을 case 3 = / 처리해주고 idx +1 해준다
값은 8/3 = 2.6666 , idx는 4 그리고 다시 재귀한다 dfs(8/3,4)
재귀 호출이 종료되었다 왜? idx(깊이) 의 값이 4가 되었기 때문
즉 모든 연산자가 한번씩 사용된 결과 라는 말
다시말해서 처음으로 (idx = N) 의 값을 만족했다는 말이다
나온 결과값을 num와 비교하여 MAX,MIN에 각각 저장해둔다 그리고 돌아가며 다시 소모한 연산자들을 다시 증가시켜준다.
if (idx == N) {
MAX = Math.max(MAX, num);
MIN = Math.min(MIN, num);
return;
}
위 과정이 표에서의 3줄이다.
모든과정을 탐색해줄 dfs를 만들었으니 이제 입력해줄 코드를 만들자
public class training {
public static int MAX = Integer.MIN_VALUE; // 최대값
public static int MIN = Integer.MAX_VALUE; // 최소값
public static int[] operator = new int[4]; // 연산자 개수
public static int[] number; // 숫자
public static int N; // 숫자 개수
//main과 dfs 모두에서 사용되기 때문에 밖으로 빼두었다.
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt(); // 첫줄 입력하는 숫자의 개수
number = new int[N]; // 숫자의 개수만큼 배열생성
// 배열에 숫자들을 넣어준다
for (int i = 0; i < N; i++) {
number[i] = in.nextInt();
}
// 배열에 연산자들의 개수를 넣어준다
for (int i = 0; i < 4; i++) {
operator[i] = in.nextInt();
}
dfs(number[0], 1);
System.out.println(MAX);
System.out.println(MIN);
}
코드전문
public class training {
public static int MAX = Integer.MIN_VALUE; // 최대값
public static int MIN = Integer.MAX_VALUE; // 최소값
public static int[] operator = new int[4]; // 연산자 개수
public static int[] number; // 숫자
public static int N; // 숫자 개수
//main과 dfs 모두에서 사용되기 때문에 밖으로 빼두었다.
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt(); // 첫줄 입력하는 숫자의 개수
number = new int[N]; // 숫자의 개수만큼 배열생성
// 배열에 숫자들을 넣어준다
for (int i = 0; i < N; i++) {
number[i] = in.nextInt();
}
// 배열에 연산자들의 개수를 넣어준다
for (int i = 0; i < 4; i++) {
operator[i] = in.nextInt();
}
dfs(number[0], 1);
System.out.println(MAX);
System.out.println(MIN);
}
public static void dfs(int num, int idx) {
for (int i = 0; i < 4; i++) { //연산자 개수 4개 배열 0,1,2,3
// 연산자의 개수가 하나라도 남아있으면 if문으로 들어온다
if (operator[i] > 0) {
// 사용되는 연산자 1감소
operator[i]--;
//연산자 계산식
switch (i) {
case 0 : dfs(num + number[idx], idx + 1); break;
case 1 : dfs(num - number[idx], idx + 1); break;
case 2 : dfs(num * number[idx], idx + 1); break;
case 3 : dfs(num / number[idx], idx + 1); break;
}
// 백트래킹 연산자 개수를 돌려놓음
operator[i]++;
}
}
}
결과
