본문 바로가기
Programming/Algorithm

백준 2169 로봇 조종하기 정답 참조

by OKOK 2018. 4. 3.

1. dp 문제이지만, 매우 유용합니다.

2. 위, 오, 왼쪽의 크기를 비교하면서 dmap 을 만들어 냅니다.

3. 먼저 위에서 오는 것 다 저장,

4. 왼쪽에서 오는 것과 비교

5. 오른쪽에서 오는 것과 비교

6. 그리고 그 중 가장 큰 값을 dmap 에 저장하면서 내려가도록 합니다.


d_map 으로 적는게 가시적으로 좋아 보입니다.

연습하면 나아지리라 생각됩니다. 



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
66
67
/*
2018.04.03 로봇 조종하기
무선 조종 로봇을 보냈습니다. 
탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하세요.
디피 문제입니다.
dmap을 만들어서, 위와 오른쪽에서 오는 것, 위와 왼쪽에서 오는 것, 그리고 이 2개중에 최대가 되는 것을 합하면서 나가도록 합니다.
*/
 
#include <iostream>
#include <algorithm>
#define SIZE 1005 // 1005
using namespace std;
int map[SIZE][SIZE];
int dmap[SIZE][SIZE];
 
int x, y, nx, ny;
int store[2][SIZE]; // 0 이, 위와 오른쪽 비교, 1이 위와 왼쪽 비교 입니다.
int N, M;
 
void problemIn() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }
}
 
void solve() {
 
    // 1 행에 대해서 처리를 합니다.
    dmap[0][0= map[0][0];
    for (int j = 1; j < M; j++) {
        dmap[0][j] = map[0][j] + dmap[0][j - 1];
    }
 
    for (int i = 1; i < N; i++) {
 
        // 위에서 내려왔을때 크기
        for (int j = 0; j < M; j++) {
            store[0][j] = store[1][j] = dmap[i - 1][j] + map[i][j]; // 일단 store 에 내려왔을때의 값을 저장해둡니다.
        }
 
        // 왼쪽에서 왔을 때
        for (int j = 1; j < M; j++) {
            store[0][j] = max(store[0][j], store[0][j-1]+map[i][j]);
        }
 
        // 오른쪽에서 돌아 왔을 때
        for (int j = M - 2; j >= 0; j--) {
            store[1][j] = max(store[1][j], store[1][j+1+ map[i][j]);
        }
 
        // 위,인,오 중에 가장 큰 값을 저장합니다.
        for (int j = 0; j < M; j++) {
            dmap[i][j] = max(store[0][j], store[1][j]);
        }
    }
}
 
int main() {
    problemIn();
    solve();
    cout << dmap[N - 1][M - 1<< endl;
    return 0;
}
cs