[백준 17265번] 나의 인생은 수학과 함께 (C++)

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

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, minV = MAX, maxV = -MAX;
int dx[] ={1, 0}, dy[] = {0, 1};
char arr[5][5];

void dfs(int y, int x, int n)
{
    if(y==N-1 && x==N-1)
    {
        minV = min(minV, n); //최솟값, 최댓값 갱신
        maxV = max(maxV, n);
        return;
    }

    for(int i=0; i<2; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny >= N || nx >= N) continue;

        int tmp = n; //원본 값 유지
        if(arr[y][x] == '-') tmp -= arr[ny][nx] - '0'; //각 연산
        if(arr[y][x] == '+') tmp += arr[ny][nx] - '0';
        if(arr[y][x] == '*') tmp *= arr[ny][nx] - '0';

        dfs(ny, nx, tmp);
    }

}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            cin >> arr[i][j];
        }
    }

    dfs(0, 0, arr[0][0]-'0');

    cout << maxV << " " << minV;
    return 0;
}

 

dfs로 어렵지 않게 풀 수 있는 문제이다.

입력 값에 부호도 있으므로 처음부터 문자 형태로 값을 입력받고 해당 값에 -'0'을 통해 숫자로 만들어준다.

현재 값이 부호면 입력 값 형태 상 다음 값은 무조건 숫자이므로 숫자로 변환후 현재 부호에 따른 값을 연산해주면 된다.

 

그리고 원본 값 유지를 통해 처음 입력받은 첫 번째 값을 시작으로, 해당 값을 tmp에 담고 해당 tmp을 통해 계산을 해주어야 한다.

그냥 n을 계산 과정에서 계속 사용한다면 dfs를 통해 현재 경로를 끝까지 탐색후 다시 원래 위치에서 다른 경로를 탐색할  때 훼손된 값을 사용하게 된다.