[C++] 이동하기 (백준 11048번)

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

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dx[3] = {1, 0, 1};
int dy[3] = {0, 1, 1};
vector<vector<int>> a;

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

    int n, m;
    cin >> n >> m;

    a = vector<vector<int>>(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    queue<vector<int>> q;
    q.push({0, 0, a[0][0]});
    int ans = 0;

    while (!q.empty()) {
        int r = q.front()[0];
        int c = q.front()[1];
        int cnt = q.front()[2];
        q.pop();
        for (int k = 0; k < 3; k++) {
            int nr = r + dx[k];
            int nc = c + dy[k];
            if (nr == n - 1 && nc == m - 1) {
                ans = max(ans, cnt + a[nr][nc]);
            } else if (nr < n && nc < m) {
                q.push({nr, nc, cnt + a[nr][nc]});
            }
        }
    }

    cout << ans << '\n';
}

처음엔 bfs로 풀었다. 당연히 메모리 초과. 너무나 dp의 정석 같은 문제인데 어째서 그런 생각을 했을까... 감다뒤;; (MLE)

 

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

int dx[3] = {1, 0, 1};
int dy[3] = {0, 1, 1};
vector<vector<int>> a;

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

    int n, m;
    cin >> n >> m;

    a = vector<vector<int>>(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    for (int i = 1; i < n; i++) a[i][0] += a[i - 1][0];
    for (int j = 1; j < m; j++) a[0][j] += a[0][j - 1];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            a[i][j] += max(a[i - 1][j], a[i][j - 1]);
        }
    }

    cout << a[n - 1][m - 1] << '\n';
}

(AC)

 

헤헤