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

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

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

이 문제 분류가 DP로 되어있는데 값을 계속해서 기록하면서 최신화해서 DP인건가 아직 DP 개념이 안잡혀있어서 왜 DP인지 잘 모르겠다. 나는 재귀함수로 완전탐색을 구현했는데 어처피 맵의 크기도 매우 작기 때문에 완전탐색을 이용해서 해결하여도 충분하다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321987654
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
int maxV = -INF;
int minV = INF;
char board[6][6];

const int dy[] = { 1,0 };
const int dx[] = { 0,1 };

bool isValid(int y, int x) {
	return (0 <= y && y < N && 0 <= x && x < N);
}

void path(int y, int x, int prev, char op) {
	for (int i = 0; i < 2; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (isValid(ny, nx)) {
			if (board[ny][nx] == '+') path(ny, nx, prev, '+');
			else if (board[ny][nx] == '-') path(ny, nx, prev, '-');
			else if (board[ny][nx] == '*') path(ny, nx, prev, '*');
			else {
				int Temp;
				if (op == '+') Temp = prev + (board[ny][nx] - '0');
				else if (op == '-') Temp = prev - (board[ny][nx] - '0');
				else if (op == '*') Temp = prev * (board[ny][nx] - '0');

				if (ny == N - 1 && nx == N - 1) {
					maxV = max(maxV, Temp);
					minV = min(minV, Temp);
					return;
				}

				path(ny, nx, Temp, board[ny][nx]);
			}
		}
	}
}

int main() {
	CUNLINK;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	path(0, 0, board[0][0] - '0', board[0][0]);

	cout << maxV << " " << minV << endl;

	return 0;
}