[99클럽 코테 스터디 20일차 TIL] 나의 인생에는 수학과 함께

 

20일차 문제 

링크 : https://www.acmicpc.net/problem/17265

 

 

 

문제 풀이

import java.util.*;
import java.io.*;

public class Main {
    static int N;
    static char[][] arr;
    static int maxVal = Integer.MIN_VALUE;
    static int minVal = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new char[N][N];

        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = st.nextToken().charAt(0);
            }
        }

        // 출발지는 arr[0][0] (숫자)
        DFS(0, 0, arr[0][0] - '0', ' '); // 처음엔 숫자만 있고 연산자는 없으므로 ' '로 전달

        System.out.println(maxVal + " " + minVal);
    }

    private static void DFS(int x, int y, int currentVal, char currentOper) {
        // 종료 조건: (N-1, N-1) 도달 시
        if (x == N - 1 && y == N - 1) {
            maxVal = Math.max(currentVal, maxVal);
            minVal = Math.min(currentVal, minVal);
            return;
        }

        // 오른쪽이나 아래쪽으로 이동
        if (x < N - 1) {
            char nextCell = arr[x + 1][y];

            if (nextCell >= '0' && nextCell <= '9') {
                // 숫자일 경우 계산을 진행
                int nextValue = nextCell - '0';
                DFS(x + 1, y, calculate(currentVal, nextValue, currentOper), currentOper);
            } else {
                // 연산자일 경우, 연산자를 바꾸고 계산
                DFS(x + 1, y, currentVal, nextCell);
            }
        }

        if (y < N - 1) {
            char nextCell = arr[x][y + 1];

            if (nextCell >= '0' && nextCell <= '9') {
                // 숫자일 경우 계산을 진행
                int nextValue = nextCell - '0';
                DFS(x, y + 1, calculate(currentVal, nextValue, currentOper), currentOper);
            } else {
                // 연산자일 경우, 연산자를 바꾸고 계산
                DFS(x, y + 1, currentVal, nextCell);
            }
        }
    }

    // 연산을 계산하는 함수
    private static int calculate(int depth, int num, char oper) {
        switch (oper) {
            case '+':
                return depth + num;
            case '-':
                return depth - num;
            case '*':
                return depth * num;
            default:
                return num; // 처음엔 연산자가 없으면 그대로 반환
        }
    }
}