백준17265 - 나의 인생에는 수학과 함께

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

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

재귀 호출 함수에 관한 문제이다. 연산자(+, -, *)를 만날 때는 계산을 하지 않고 저장해 놓았다가 숫자를 만나면 이전에 저장해 놓은 연산자를 사용하여 연산한 결과를 얻는다. 이렇게 끝까지 연산을 한 결과중에 가장 큰 값과 작은 값을 찾으면 되는 문제이다. 

 

#include <iostream>
#include <algorithm>
using namespace std;

int small = 100000000; //최소 결과, 처음은 매우 큰 수로 지정
int big = -100000000; //최대 결과, 처음은 매우 작은 수로 지정
int n; //변의 길이

//오른쪽과 아래로만 이동 가능
int dx[] = { 1, 0 }; //행으로 이동하는 범위
int dy[] = { 0, 1 }; //열로 이동하는 범위

char mat[6][6]; //주어진 칸의 상태

//재귀를 통한 최댓값과 최솟값 찾기
void rec(int x, int y, int ans, char what) { //행의 값, 열의 값, 현재까지 진행한 연산의 결과, 직전에 만난 칸의 정보
	for (int i = 0; i < 2; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (1 <= nx && nx <= n && 1 <= ny && ny <= n) { //이동한 결과가 칸 안에 있는 경우
			if (mat[nx][ny] == '+') { //+를 만난 경우
				rec(nx, ny, ans, '+');
			}
			else if (mat[nx][ny] == '-') { //-를 만난 경우
				rec(nx, ny, ans, '-');
			}
			else if (mat[nx][ny] == '*') { //*를 만난 경우
				rec(nx, ny, ans, '*');
			}
			else { //숫자를 만난 경우
				int check; //현재 연산의 결과를 저장
				if (what == '+') { //직전에 만난 칸이 덧셈인 경우
					check = ans + (mat[nx][ny] - '0');
				}
				else if (what == '-') { //직전에 만난 칸이 뺄셈인 경우
					check = ans - (mat[nx][ny] - '0');
				}
				else if (what == '*') { //직전에 만난 칸이 곱셈인 경우
					check = ans * (mat[nx][ny] - '0');
				}
				if (nx == n && ny == n) { //이동한 결과가 마지막 칸인 경우
					big = max(big, check); //최댓값을 찾는다.
					small = min(small, check); //최솟값을 찾는다.
					return; //함수 종료
				}
				rec(nx, ny, check, mat[nx][ny]);
			}
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> mat[i][j];
		}
	}

	rec(1, 1, mat[1][1] - '0', mat[1][1]); //재귀 시작

	cout << big << ' ' << small;
}