[BAEKJOON] 14888 연산자 끼워넣기

문제 요약

• 알고리즘 분류: 백트래킹
• 난이도: Silver1
• 문제내용:
  • 숫자 N개와 연산자 N-1개를 준다.
  • 숫자 사이에 연산자를 넣는다.
  • 계산방식
    • 연산방식은 기존 연산순위가 아닌 앞에 숫자부터 연산하는 방식으로 간다
    • 나눌때는 나머지 제외한 값으로 계산한다.
• 사이트 주소: https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

문제풀이

 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9

백트래킹 - 나무위키

 이번 문제는 숫자중간에 넣어서 전체를 계산하는 방식이 아니라 앞에서 부터 차례대로 계산하는 방식이다. 그리고 연산자의 개수가 고정으로 있어서 각 연산자를 count를 해서 분기처리하면 되서 백트레킹 기본을 알면 풀수가 있어서 접근은 쉽다. 다만 코드 작성하는것이 좀 번거로울뿐이다.

1.  전역변수로 최대값, 최소값을 설정한다.
2. 초기에는 맨앞에 숫자와 연산자 카운터 배열이나 리스트 초기 검색할 인덱스를 1로 설정한다.
3.  연산후 N개까지 도달 했을경우 최대 최소 값을 비교하면서 최대값, 최소값을 저장한다.
4. N개까지 도달 하지 않았을 경우 연산자의 개수가 초과 되지 않았을경우 인덱스 위치와 연산한후 연산된것을 감소시키고 인덱스 위치는 +1한다음 함수 재호출한다.
5. 함수가 끝났을때 최대, 최소값을 출력한다.

Code

Python

def operate(n, p, mi, mu, di, number, s):
    global max_value, min_value
    if n == N:
        max_value = max(max_value, number)
        min_value = min(min_value, number)
        return
    
    if p > 0:
        operate(n + 1, p - 1, mi, mu, di, number + numbers[n], s + '+' + str(numbers[n]))
    if mi > 0:
        operate(n + 1, p, mi - 1, mu, di, number - numbers[n], s + '-' + str(numbers[n]))
    if mu > 0:
        operate(n + 1, p, mi, mu - 1, di, number * numbers[n], s + '*' + str(numbers[n]))
    if di > 0:
        operate(n + 1, p, mi, mu, di - 1, int(number / numbers[n]), s + '//' + str(numbers[n]))
    
N = int(input())
numbers = list(map(int, input().split()))
pl, mi, mu, di = map(int, input().split())
max_value = -1e10
min_value = 1e10
operate(1, pl, mi, mu, di, numbers[0], str(numbers[0]))
print(max_value)
print(min_value)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {
	
	static int max_value = Integer.MIN_VALUE;
	static int min_value = Integer.MAX_VALUE;
	static int[] numbers;
	static int  N;
	
	public static void main(String[] args) throws IOException {
		
		int x, y;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		numbers = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
			
		for(int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		
		int plus = Integer.parseInt(st.nextToken());
		int minus = Integer.parseInt(st.nextToken());
		int mul = Integer.parseInt(st.nextToken());
		int div = Integer.parseInt(st.nextToken());
		
		operater(1, plus, minus, mul, div, numbers[0]);
		
		System.out.println(max_value);
		System.out.println(min_value);
		
	}
	
	static public void operater(int n, int pl, int mi, int mu, int di, int number) {
		if (n == N) {
			max_value = Math.max(max_value, number);
			min_value = Math.min(min_value, number);
			return;
		}
		
		if(pl > 0) {
			operater(n + 1, pl - 1, mi, mu, di, number + numbers[n]);
		}
		if(mi > 0) {
			operater(n + 1, pl, mi - 1, mu, di, number - numbers[n]);
		}
		if(mu > 0) {
			operater(n + 1, pl, mi, mu - 1, di, number * numbers[n]);
		}
		if(di > 0) {
			operater(n + 1, pl, mi, mu, di - 1, number / numbers[n]);
		}
	}
				
}