알고리즘/BOJ 문제풀이

[DP] BOJ 2169 로봇 조종하기

4Legs 2020. 12. 15. 17:55

문제 링크 : www.acmicpc.net/problem/2169

 

2169번: 로봇 조종하기

첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.

www.acmicpc.net

2차원 배열 형태의 입력에서 목적지까지의 최대 가치를 구하는 문제이다.

문제에서 로봇은 위쪽으로 이동할 수 없다는 것에 주목하자.

로봇이 위쪽으로 이동할 수 없기 때문에, 어떤 한 행에 대한 최대 가치를 구하기 위해 그 이전 행의 최대 가치들을 미리 구해놓는다는 접근이 가능하다.

 

또한 로봇은 오른쪽, 왼쪽 양방향으로 이동 가능하며, 한번 지난 칸은 이동할 수 없다는 제약을 갖고 있다.

이 말은 곧 한 행에서 로봇은 오른쪽으로만 이동하거나, 왼쪽으로만 이동할 수 있다는 것과 같다.

이제 이렇게 세운 계획을 통해 구체적인 해결 방법을 구상해 보자.

 

■ 1행의 경우

dp의 끝 인덱스 0은 해당 값이 실제로 그 칸까지 도달하는 데의 최대 가치임을 의미한다.

 

 1행 이후의 경우

 

[코드]

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define MINF -99999999
 
using namespace std;
typedef pair<intint> p;
 
int board[1001][1001];
int dp[1001][1001][3];
int n, m;
 
void get_dp() {
    for (int row = 2; row <= n; row++) {
        //좌 -> 우로 가는 최대가치 갱신
        dp[row][1][1= dp[row - 1][1][0+ board[row][1];
        for (int col = 2; col <= m; col++) {
            int dpval = max(dp[row - 1][col][0], dp[row][col - 1][1]) + board[row][col];
            dp[row][col][1= max(dp[row][col][1], dpval);
        }
 
        //우 -> 좌로 가는 최대가치 갱신
        dp[row][m][2= dp[row - 1][m][0+ board[row][m];
        for (int col = m - 1; col >= 1; col--) {
            int dpval = max(dp[row - 1][col][0], dp[row][col + 1][2]) + board[row][col];
            dp[row][col][2= max(dp[row][col][2], dpval);
        }
 
        //최종 dp값 결정
        for (int col = 1; col <= m; col++)
            dp[row][col][0= max(dp[row][col][1], dp[row][col][2]);
    }
}
 
void init() {
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            cin >> board[i][j];
            for (int k = 0; k < 3; k++) dp[i][j][k] = MINF;
        }
 
    int sum = 0
    for (int i = 1; i <= m; i++) {
        for (int k = 0; k < 3; k++) dp[1][i][k] = sum + board[1][i];
        sum += board[1][i];
    }
 
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    get_dp();
 
    printf("%d\n", dp[n][m][0]);
 
    return 0;
}
cs

 

'알고리즘 > BOJ 문제풀이' 카테고리의 다른 글

[Segtree] BOJ 7578 공장  (0) 2020.12.22
[Graph] BOJ 1766 문제집  (0) 2020.12.21
[Dijkstra] BOJ 13907 세금  (0) 2020.12.14
[Greedy] BOJ 9576 책 나눠주기  (0) 2020.12.06
[Greedy] BOJ 1781 컵라면  (0) 2020.12.03