백준 - 17265번 : 나의 인생에는 수학과 함께 (C++)

풀이 방법 : DFS

N이 작아서 사실 어떤 방식으로 풀어도 되는 문제다. 만약 N이 컸다고 한다라면 DP 테이블 추가해서 풀면 해결이 가능할 것 같다.

입력에서 숫자와 연산자가 무조건 번갈아 나온다고 했으니 그냥 단순하게 아래, 오른쪽으로만 이동하면서 연산자에 따라 숫자를 계산하고, 끝에 도달했을 때 최대, 최솟값을 갱신 해주면 된다.

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int N;
char Map[5][5] = {};
int DirY[2] = { 0, 1 };
int DirX[2] = { 1, 0 };
int Min = INT_MAX;
int Max = INT_MIN;

void DFS(int CurY, int CurX, int CurNum, char PrevOperator)
{
	if (CurY == N - 1 && CurX == N - 1)
	{
		Min = min(CurNum, Min);
		Max = max(CurNum, Max);
		return;
	}

	for (int i = 0; i < 2; ++i)
	{
		int NextY = CurY + DirY[i];
		int NextX = CurX + DirX[i];

		bool IsInBound = NextY >= 0 && NextY < N && NextX >= 0 && NextX < N;

		if (!IsInBound)
			continue;

		if (Map[NextY][NextX] == '+' || Map[NextY][NextX] == '-' || Map[NextY][NextX] == '*')
		{
			DFS(NextY, NextX, CurNum, Map[NextY][NextX]);
		}

		else
		{
			int Num = (int)Map[NextY][NextX] - (int)'0';
			int NextNum = CurNum;
			switch (PrevOperator)
			{
			case '+':
				NextNum += Num;
				break;
			case '-':
				NextNum -= Num;
				break;
			case '*':
				NextNum *= Num;
				break;
			}

			DFS(NextY, NextX, NextNum, ' ');
		}
	}
}

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	cin >> N;

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

	DFS(0, 0, (int)Map[0][0] - (int)'0', ' ');
	
	cout << Max << ' ' << Min;
}