[백준][2169번][DP] 로봇 조종하기

로봇 조종하기

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

<코드>

#include <stdio.h>
int map[1000][1000];
int primap[1000][1000];
 
int Max(int a, int b)
{
    return a > b ? a : b;
}
 
int main(void){
    
    int N, M;
 
    int line[2][1000];
 
    int total = 0;
 
    scanf("%d %d", &N, &M);
    // 입력
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%d", &map[i][j]);
 
    primap[0][0] = map[0][0];
    for (int i = 1; i < M; i++)
    {
        primap[0][i] = primap[0][i - 1] + map[0][i];
    }
 
    for (int height = 1; height < N; height++)
    {
        // 한번 저장
        for (int row = 0; row < M; row++)
            line[0][row] = line[1][row] = primap[height - 1][row] + map[height][row];
 
        for (int row = 1; row < M; row++)
            line[0][row] = Max(line[0][row], line[0][row-1]+map[height][row]);
 
        for (int row = M-2; row >= 0; row--)
            line[1][row] = Max(line[1][row], line[1][row + 1] + map[height][row]);
 
        for (int row = 0; row < M; row++)
            primap[height][row] = Max(line[0][row], line[1][row]);
 
    }
    
    printf("%d\n", primap[N - 1][M - 1]);
 
    return 0;
}

<문제 푼 방법>

1. 이 문제는 DP(dynamic programing) 이다.

2. 가장 중요한 것은 각 위치에 대해서 최대치를 매번 구해야 한다. 즉 과거의 정보들이 현재의 최대치를 만드는데 도움을 준다. 

3. 여기서 계산할 시 특징중 하나가 뒤로 못 돌아가기 때문에 '(오른쪽)-------------->' 방향과 '<------------------(왼쪽)' 방향 그리고 위에서 오는 방향만 있다.

4. 즉 계산시 두 부분으로 생각해서 계산 하였습니다. 처음은 오른쪽에서 오는 값과 위쪽에서 오는 값을 비교하여서 큰값을 저장하는 배열1 과 왼쪽에서 오는 값과 위쪽에서 오는 값을 비교하여서 큰값을 저장하는 배열 2를 만들고 이 두 배열을 비교 가장 큰 값을 현재의 값으로 만들어 주게 하였습니다. 

5. 즉 4의 방식으로 쭈욱 진행하다보면 각 포인트마다 알 수 있는 최대 값에 대해서 알 수 있습니다.