취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17265번 문제인 나의 인생에는 수학과 함께이다.
문제는 아래 링크를 확인하자.

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

오른쪽 이동 5회와 아래쪽 이동 5회의 순서를 정할 경우의 수는 252가지로 충분히 적은 경우의 수이다.

모든 이동가능한 경로를 따라 이동하며 각 경우의 경로의 값을 계산해 그중 최댓값과 최솟값을 찾는 것으로 문제를 해결해주자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
char board[5][5];
int mx = -1000000007, mn = 1000000007;

void func(int r, int c, int val) {
	if (r == N - 1 && c == N - 1) {
		mx = max(mx, val), mn = min(mn, val);
		return;
	}

	if (r + 2 < N) {
		if (board[r + 1][c] == '+') func(r + 2, c, val + (int)(board[r + 2][c] - '0'));
		else if (board[r + 1][c] == '-') func(r + 2, c, val - (int)(board[r + 2][c] - '0'));
		else func(r + 2, c, val * (int)(board[r + 2][c] - '0'));
	}
	if (r + 1 < N && c + 1 < N) {
		if (board[r + 1][c] == '+') func(r + 1, c + 1, val + (int)(board[r + 1][c + 1] - '0'));
		else if (board[r + 1][c] == '-') func(r + 1, c + 1, val - (int)(board[r + 1][c + 1] - '0'));
		else func(r + 1, c + 1, val * (int)(board[r + 1][c + 1] - '0'));
		if (board[r][c + 1] == '+') func(r + 1, c + 1, val + (int)(board[r + 1][c + 1] - '0'));
		else if (board[r][c + 1] == '-') func(r + 1, c + 1, val - (int)(board[r + 1][c + 1] - '0'));
		else func(r + 1, c + 1, val * (int)(board[r + 1][c + 1] - '0'));
	}
	if (c + 2 < N) {
		if (board[r][c + 1] == '+') func(r, c + 2, val + (int)(board[r][c + 2] - '0'));
		else if (board[r][c + 1] == '-') func(r, c + 2, val - (int)(board[r][c + 2] - '0'));
		else func(r, c + 2, val * (int)(board[r][c + 2] - '0'));
	}
}

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

	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
		}
	}

	func(0, 0, board[0][0] - '0');

	cout << mx << ' ' << mn;
}