[백준 - Java] 17265번 : 나의 인생에는 수학과 함께

문제

www.acmicpc.net/problem/17265

 

세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 계산하고 한걸음 한걸음 보폭을 계산하여 자신의 활동량을 확인하며 인생의 목표를 실행하며 살아가고 있다.  그런 세현이는 매일 학교를 가면서 지나가는 길에도 수학을 적용시키고 싶었다.

세현이네 집에서 학교까지 가는 길은 N x N 크기의 바둑판과 같다. 그리고 각 블록은 1x1 정사각형으로 구분 지을 수 있다. 세현이는 그 블록마다 숫자와 연산자가 존재한다고 생각해서 임의의 숫자와 연산자를 각 블록에 넣어 바둑판을 만들었다.

세현이는 학교에서 집으로 가는 경로에서 만나는 숫자와 연산자의 연산 결과의 최댓값과 최솟값을 구하려고 한다. 세현이는 항상 자신의 집 (1, 1)에서 학교 (N, N)까지 최단거리로 이동한다. 최단거리로 이동하기 위해서는 오른쪽과 아래쪽으로만 이동해야 한다.

 

 

위와 같이 N = 5 인 5 x 5 바둑판을 만들었다고 해보자.

그림 1의 경로를 통해 집(1, 1)에서 학교(N, N)까지 어떻게 연산이 되는지 확인해보자. 경로에서 만나는 연산자들의 우선순위는 고려하지 않는다.

 

1.  5 → × → 4 = 20
2.  20 → + → 5 = 25
3.  25 → ×→ 5 = 125
4.  125 → + → 2 = 127

그림 1은 최댓값을 가지는 경로이며 127이라는 최댓값을 얻을 수 있다.

그리고 위와 같이 연산하여 그림 2의 경로를 통해서 최솟값으로 3을 얻을 수 있다.

세현이는 이 길을 걸으면서 최댓값과 최솟값을 암산하다가 교통사고를 당해 현재 인하대학교 병원에 입원했다. 아픈 세현이를 위해 최댓값과 최솟값을 구해주자.

입력

첫 번째 줄에는 지도의 크기 N이 주어진다. (3 ≤ N ≤ 5, N은 홀수) 

그 다음 N 줄에는 N개의 숫자 또는 연산자가 빈칸을 사이에 두고 주어지며, 세현이네 집 (1, 1)과 학교 (N, N)는 반드시 숫자로 주어진다.

그리고 숫자 다음에는 연산자, 연산자 다음에는 숫자가 나오도록 주어진다. 주어지는 숫자는 0이상 5이하의 정수, 연산자는 (‘+’, ‘-’, ‘*’) 만 주어진다.

출력

연산 결과의 최댓값과 최솟값을 하나의 공백을 두고 출력한다. 연산자 우선순위는 고려하지 않는다.

 

예제 입력

5

5 + 5 - 3

* 3 - 1 -

4 + 5 + 2

- 2 * 3 -

1 * 5 + 2

예제 출력

127 3

 

DFS를 돌며 완전 탐색해 구현

1. 첫 번째 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static int min = Integer.MAX_VALUE;
	public static int max = Integer.MIN_VALUE;
	
	//아래쪽, 오른쪽 이동을 위한 변수
	public static int[] dx = {1, 0};
	public static int[] dy = {0, 1};
	
	public static int n;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		n = N;
		String[][] map = new String[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				map[i][j] = sc.next();
			}
		}
		
		dfs(0, 0, Integer.parseInt(map[0][0]), map[0][0], map);
		System.out.println(max + " " + min);
	}
	
	public static void dfs(int x, int y, int ans, String what, String[][] map) {
		for(int i = 0; i < 2; i++) { //첫 번째 숫자 / 연산자 / 두 번째 숫자 순이기 때문에 i < 2;
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <= n-1 && ny <= n-1) { //이차원 배열의 범위 안에 있을 때
				if(map[nx][ny].equals("+")) {
					dfs(nx, ny, ans, "+", map);
				} else if(map[nx][ny].equals("-")) {
					dfs(nx, ny, ans, "-", map);
				} else if(map[nx][ny].equals("*")) {
					dfs(nx, ny, ans, "*", map);
				} else { //숫자일 경우 
					int result = 0;
					
					if(what.equals("+")) { //이전의 값이 연산자일 경우 계산
						result = ans + Integer.parseInt(map[nx][ny]);
					} else if(what.equals("-")) {
						result = ans - Integer.parseInt(map[nx][ny]);
					} else if(what.equals("*")) {
						result = ans * Integer.parseInt(map[nx][ny]);
					} 
                    
					//(N, N) 마지막일 경우 min, max 구하기
					if(nx == n-1 && ny == n-1) {
						max = Math.max(max, result);
						min = Math.min(min, result);
						
						return;
					}
                    
					dfs(nx, ny, result, map[nx][ny], map);
				}
			}
		}
	}
}

2. 두 번째 코드

import java.util.Scanner;

public class Main2 {
	public static int min = Integer.MAX_VALUE;
	public static int max = Integer.MIN_VALUE;

	public static int n;
	public static char[][] mat;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		n = N;
		mat = new char[N][N];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				mat[i][j] = sc.next().charAt(0);
			}
		}

		dfs(0, 0, mat[0][0]-'0', mat[0][0]);
		System.out.println(max + " " + min);
	}

	public static void dfs(int x, int y, int pre, char oper) {
		int temp = mat[x][y] - '0';
		if(temp >= 0 && temp <= 5) { //temp가 숫자인 경우 
			if(oper == '+')
				pre += temp;
			else if(oper == '-')
				pre -= temp;
			else if(oper == '*')
				pre *= temp;
		} else { //temp가 연산자인 경우 
			oper = mat[x][y];
		}
		
		//(n, n)까지 다 확인한 경우 종료 
		if(x == n-1 && y == n-1) {
			max = Math.max(pre, max);
			min = Math.min(pre, min);
			return;
		}

		//아래쪽으로 한 칸 이동 
		if(x < n-1) {
			dfs(x+1, y, pre, oper);
		}

		//오른쪽으로 한 칸 이동 
		if(y < n-1) {
			dfs(x, y+1, pre, oper);
		}
	}

}

3. BufferedReader / StringTokenizer 사용하면 72ms로 최소로 시간 걸림

GITHUB

github.com/KwonMinha/BOJ/tree/master/BOJ%2317265/src

KwonMinha/BOJ