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

개요

문제 링크
골드 5, DP
사칙연산을 수행하며 경로를 이동할 때 최종값의 최대최소

---

접근

1. 단순한 2차원 경로탐색 dp인데, 문자열이 들어가면서 + 최대최소를 모두 물어보면서 까다로워진 케이스.
2. dp[i][j]에는 (i,j) 까지 오면서 얻은 최댓값을 저장하고, 업데이트는 어디와 비교하느냐? 하면 세 지점과 비교하면 됨. 왼쪽위, 두칸 왼쪽, 두칸 위. 나머지는 크게 복잡한 것이 없고 실수만 안하면 됨

---

Pseudo code

for (y = 세로)
    for(x = 가로)
        left_up = dp[y-1][x-1] 연산자 dp[y][x]
        two_left = dp[y][x-2] 연산자 dp[y][x]
        two_up = dp[y-2][x] 연산자 dp[y][x]
        dp[y][x] = max_or_min(left_up, two_left, two_up)

---

Source code

#include <bits/stdc++.h>
using namespace std;

int calc(int a, char b, char c) {
    c -= '0';
    if (b=='+')
        return a+c;
    if (b=='-')
        return a-c;
    if (b=='*')
        return a*c;
    return 0;
}

int main() {
    int n;
    char x;
    cin >> n;
    char a[n][n];
    int dp[n][n][2];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            cin >> a[i][j];
    int l, u, p, q;
    dp[0][0][0] = a[0][0]-'0';
    dp[0][0][1] = a[0][0]-'0';
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            if ((i+j)%2 == 0) {
                if (i==0 && j==0)
                    continue;
                p = -2e9, q = 2e9;
                if (i >= 1 && j >= 1) {
                    u = calc(dp[i-1][j-1][0],a[i-1][j],a[i][j]);
                    l = calc(dp[i-1][j-1][0],a[i][j-1],a[i][j]);
                    p = max(l, u);
                    u = calc(dp[i-1][j-1][1],a[i-1][j],a[i][j]);
                    l = calc(dp[i-1][j-1][1],a[i][j-1],a[i][j]);
                    q = min(l, u);
                }
                if (i >= 2) {
                    u = calc(dp[i-2][j][0],a[i-1][j],a[i][j]);
                    p = max(p, u);
                    u = calc(dp[i-2][j][1],a[i-1][j],a[i][j]);
                    q = min(q, u);
                }
                if (j >= 2) {
                    l = calc(dp[i][j-2][0],a[i][j-1],a[i][j]);
                    p = max(p, l);
                    l = calc(dp[i][j-2][1],a[i][j-1],a[i][j]);
                    q = min(q, l);
                }
                dp[i][j][0] = p;
                dp[i][j][1] = q;
            }

    cout << dp[n-1][n-1][0] << " " << dp[n-1][n-1][1];
}