17265 나의 인생에는 수학과 함께

 

 

1. 풀이

 

dfs를 이용해서 풀면된다.

 

(1,1) 에서 시작해서,

max 배열에는 연산 결과가 큰 값으로,

min 배열에는 연산 결과가 작은 값으로 채우면 된다.

그 후 max[N][N] 과, min[N][N] 을 출력하면 정답이 된다.

 

아래 그림은 예제에서 일부분을 가져온 것이다.

5가 입력되어 있는 부분은 (1,1)의 위치이다.

이 때,

(2,2) 위치에는

두가지 연산이 있다.

 

 

1) 오른쪽, 아래 이동

 

5+3 = 8 이 먼저 연산되었다고 하자. 

 

그러면 max[2][2] = 8 이 된다.

 

 

2) 아래, 오른쪽 이동

 

 

그 이후에 아래, 오른쪽 이동으로 

5 * 3 = 15 가 결과로 나왔다면

 

더 큰 값, 15로 바꿔주어 

max[2][2] = 15 가 된다.

 

 

 

2. 최종 코드

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

public class Main {
	
	static int N;
	static String input[][];
	static int max[][];
	static int min[][];
	
	
	public static void main(String[] args) throws IOException {
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		input = new String[N+1][N+1];
		
		for(int i=1; i<=N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j=1; j<=N; j++) {
				input[i][j] = st.nextToken();
			}
		}
	
		max  = new int[N+1][N+1];
		min  = new int[N+1][N+1];
		
		for(int i=0; i<=N; i++) {
			Arrays.fill(min[i], Integer.MAX_VALUE);
		}
		
		for(int i=0; i<=N; i++) {
			Arrays.fill(max[i], Integer.MIN_VALUE);
		}
		
		max[1][1] = Integer.parseInt(input[1][1]);
		min[1][1] =  Integer.parseInt(input[1][1]);
		
		dfs(1,2, Integer.parseInt(input[1][1]), input[1][2], true);
		dfs(1,2, Integer.parseInt(input[1][1]), input[1][2], false);
		dfs(2,1, Integer.parseInt(input[1][1]), input[2][1], true);
		dfs(2,1, Integer.parseInt(input[1][1]), input[2][1], false);
		
		System.out.println(max[N][N] + " " + min[N][N]);
		
	}
	
	public static void dfs(int x, int y, int number, String a, boolean check) {
	
			int dx [] = {0,1};
			int dy [] = {1,0};
			int result=0;
			int nx = 0;
			int ny = 0;
	
			if(((x+y)%2)!=0) {
				
				for(int i=0; i<2; i++ ) {
					nx = x + dx[i];
					ny = y + dy[i];
					
					if(nx>0 && ny >0 && nx<=N && ny<=N) {
						
					dfs(nx, ny, number, input[x][y], check);
			      }
					
			   }
			}else {
				
				if(a.equals("+")) {
					
					result = number + Integer.parseInt(input[x][y]);						
						
				}else if(a.equals("-")) {
						
					result = number - Integer.parseInt(input[x][y]);
				
				}else if(a.equals("*")) {
						
					result = number * Integer.parseInt(input[x][y]);
					
				}
				
				max[x][y] = Math.max(max[x][y], result);
				min[x][y] = Math.min(min[x][y], result);
					
				for(int i=0; i<2; i++) {
					nx = x + dx[i];
					ny = y+ dy[i];
					if(nx>0 && ny>0 && nx<=N && ny<=N) {
					
						if(check) {
							dfs(nx, ny,max[x][y], a, true);
						}else {
							dfs(nx, ny,min[x][y], a, false);
						}
					}
				}
			}
	}
	
}