[백준] 단계별로 풀어보기(단계:14,백트래킹,JAVA)14888번, 연산자 끼워넣기

문제 링크

14888번: 연산자 끼워넣기

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

백트래킹이란 깊이 우선 탐색을 바탕으로 탐색 중 오답을 만나면 이전 분기점으로 돌아가서 다른 해결방법이 있는지 확인하고 더 이상 없으면 더 이전에 분기점으로 돌아가서 해결방법을 찾아보는 방식입니다.깊이 우선 탐색은 모든 경우의 수를 검색하게 되지만 백트래킹은 오답으로 판단될시 그에 해당하는 자식 노드들은 모두 무시하고 넘어가기 때문에 더욱 효율적으로 코드가 진행됩니다.

검은색 : 실행되지 않은 노드

빨간색 : 오답으로 판단한 노드

초록색 : 올바른 값이라고 판단한 노드

위에 그림처럼 부모노드가 틀리다고 판정되면 자식노드 무시하고 이전 분기점으로 돌아가서 확인하는 방식으로 코드가 전개되어 가는 방식입니다.

 

이 문제에 경우 연산에 대한 모든 경우의 수를 확인하여 최대값 및 최소값을 구하는 것으로 깊이 우선 방식과 차이점이 없습니다.

그래서  +, -, x, ÷에 대한 수열에 연산을 재귀를 통해 모두 확인하는 방식을 사용하였습니다.

 

• 수열의 숫자를 저장할 배열 num을 만들었습니다.
• 연산자 횟수를 저장하는 배열 operator을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 연산자를 끼어넣어 최대값 및 최소값 구하는 함수 operatorInsert을 만들었습니다.
• 연산자에 대한 계산을하는 함수 operatorResult를 만들었습니다.

• 연산을 완성하면 Math.min, Math.max를 사용하여 최대값, 최소값을 구하였습니다.
• 위에 알고리즘을 토대로 sudokuSolution을 작성하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int[] num;		//수열 저장 배열
	static int[] operator = new int[4];		//연산자 횟수 저장 배열
    //최대값, 최솟값, 수열 크기
	static int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, size;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	size = Integer.parseInt(br.readLine());
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	num = new int[size];		//배열 초기화
    	
        //----------------입력값 배열에 저장------------------
    	for(int i=0;i<size;i++)
    		num[i] = Integer.parseInt(st.nextToken());
    	
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<4;i++)
    		operator[i] = Integer.parseInt(st.nextToken());
        //-----------------함수 실행 및 결과 출력------------------
    	operatorInsert(num[0], 1);
    	System.out.print(max + "\n" + min);
    	br.close();
	}
    //-------------------연산자 끼어넣기 함수-----------------
	public static void operatorInsert(int current, int depth) {
 	//----------연산 완료후 최대값 최소값 비교----------------
		if(depth==size) {
			max = Math.max(current, max);
			min = Math.min(current, min);
			return;
		}
        //-------------백트래킹을 통해 모든 경우의 수 연산-------------
			for(int j=0;j<4;j++) {
				if(operator[j]!=0) {
					operator[j]--;
					operatorInsert(operatorResult(j, depth, current), depth+1);
					operator[j]++;
				}
			}		
	}
    //----------연산자 확인하여 연산하기----------------
	public static int operatorResult(int n,int index, int current) {
		if(n==0)
			return current + num[index];
		else if(n==1)
			return current - num[index];
		else if(n==2)
			return current * num[index];
		else
			return current / num[index];
	}
}