99클럽 코테 스터디 20일차 TIL + Backtracking

문제

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

• 설명: 주어진 보드판에서 아래쪽, 오른쪽으로만 이동할 수 있을 때 최솟값, 최댓값을 구하여라

풀이

• n이 $5$라서 모든 경우의 수를 다 따지면 된다.

오늘의 회고

• 오늘 역시 잔실수가 많았다. 가장 적은 값이 음수가 될수 있었는데 최댓의 초깃값을 0으로 두어서 반례를 찾는데 한참 걸렸다.
• 이외에도 다음줄에 출력하는게 아닌데 다음줄에 출력한다든가 등 문제가 많았다.
• 더 집중해서 풀어보자

Code

// Baekjoon17265.cpp
#include <iostream>

#include <string>

using namespace std;

using pii = pair<int, int>;

const int moves[2][2] = { { 1, 0 }, { 0, 1 } };

int n;
char map[5][5];
pii ans = { -0x3f3f3f3f, 0x3f3f3f3f };

int getValue(string expr) {
    int prev = expr[0] - '0';
    for (int i = 1; i < expr.size(); i += 2) {
        if (expr[i] == '+')
            prev += expr[i + 1] - '0';
        else if (expr[i] == '-')
            prev -= expr[i + 1] - '0';
        else
            prev *= expr[i + 1] - '0';
    }

    return prev;
}

void dfs(int row, int col, string expr) {
    if (row == (n - 1) && col == (n - 1)) {
        ans.first = max(ans.first, getValue(expr));
        ans.second = min(ans.second, getValue(expr));
    } else {
        for (int i = 0; i < 2; i++) {
            int nextRow = row + moves[i][0], nextCol = col + moves[i][1];
            if ((0 <= nextRow && nextRow < n) && (0 <= nextCol && nextCol < n)) {
                expr.push_back(map[nextRow][nextCol]);
                dfs(nextRow, nextCol, expr);
                expr.pop_back();
            }
        }
    }
}

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];

    string expr;
    expr.push_back(map[0][0]);
    dfs(0, 0, expr);

    cout << ans.first << ' ' << ans.second << '\n';

    return 0;
}