백준2169 로봇 조종하기

작성일 | In

문제 링크

  • http://icpc.me/2169

문제 출처

  • 2002 KOI 고등부 1번

사용 알고리즘

  • DP

시간복잡도

  • $O(NM)$

풀이

아래/오른쪽으로만 가면 간단한 DP문제일텐데, 이 문제는 왼쪽으로도 갈 수 있습니다. 그러나 한 번 방문한 위치는 다시 방문하지 못하니 이 점에 주목해서 점화식을 세워봅시다.

한 번 방문한 위치를 다시 방문하지 못한다는 것은, 한 행에서는 동일한 방향으로만 이동할 수 있다는 것을 의미합니다.
점화식을 다음과 같이 정의합시다.

  • $L(i, j)$: $(i, j)$에 도달하는 최소 비용. 단, $i$번째 행에서는 오른쪽으로만 이동해야 한다.
  • $R(i, j)$: $(i, j)$에 도달하는 최소 비용. 단, $i$번째 행에서는 왼쪽으로만 이동해야 한다.
  • $D(i, j)$: $(i, j)$에 도달하는 최소 비용

상태 전이는 다음과 같습니다.

  • $L(i, j) = max(D(i-1, j), L(i, j-1)) + A(i, j)$
  • $R(i, j) = max(D(i-1, j), R(i, j+1)) + A(i, j)$
  • $D(i, j) = max(L(i, j), R(i, j))$

점화식은 $O(NM)$에 계산할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

int N, M, A[1010][1010], D[1010][1010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) for(int j=1; j<=M; j++) cin >> A[i][j];

    for(int i=1; i<=M; i++) D[1][i] = D[1][i-1] + A[1][i];
    for(int i=2; i<=N; i++){
        int L[1010], R[1010];
        L[1] = D[i-1][1] + A[i][1];
        R[M] = D[i-1][M] + A[i][M];
        for(int j=2; j<=M; j++) L[j] = max(D[i-1][j], L[j-1]) + A[i][j];
        for(int j=M-1;  j; j--) R[j] = max(D[i-1][j], R[j+1]) + A[i][j];
        for(int j=1; j<=M; j++) D[i][j] = max(L[j], R[j]);
    }
    cout << D[N][M];
}