[99클럽/파이썬 챌린저/25일차] 로봇 조종하기

백준 2169번 로봇 조종하기 G2

 

문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화하여 생각하기로 한다. 지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다. 각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.

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

출력
첫째 줄에 최대 가치의 합을 출력한다.

다이나믹 프로그래밍

 

우연히도 예약된 글과 동일한 문제를 제공받았다.

파이썬 및 C++로도 추가 풀이했다.

 

 

 

import sys

col, row = map(int, sys.stdin.readline().split())

dp = []
for _ in range(2):
    q = []
    for _ in range(row):
        q.append([-10000000, -10000000, -10000000])
    dp.append(q)

DOWN, LEFT, RIGHT = 0, 1, 2

floor = list(map(int, sys.stdin.readline().split()))
dp[0][0][DOWN] = floor[0]

for x in range(1, row):
    dp[0][x][LEFT] = max(dp[0][x-1][DOWN], dp[0][x-1][LEFT]) + floor[x]
y = 0
for t in range(1, col):
    y = t%2
    floor = list(map(int, sys.stdin.readline().split()))
    for x in range(row):
        dp[y][x][DOWN] = max(dp[y-1][x]) + floor[x]
    for x in range(1, row):
        dp[y][x][LEFT] = max(dp[y][x-1][DOWN], dp[y][x-1][LEFT]) + floor[x]
    for x in range(row-2,-1,-1):
        dp[y][x][RIGHT] = max(dp[y][x+1][DOWN], dp[y][x+1][RIGHT]) + floor[x]
print(max(dp[y][-1]))

 

 

#include <iostream>
#include <algorithm>

using namespace std;

int dp[2][1001][3];
int cost[1001];

void get_cost(int r)
{
    for (int i=0; i<r; ++i)
    {
        int v; cin>>v;
        cost[i] = v;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int left = 0, right = 1, down = 2;

    int n, m; cin>>n>>m;
    get_cost(m);
    int cur_i = 0;

    for (int i=0; i<2; ++i) 
        for (int j=0; j<m; ++j)
            for (int k=0; k<3; ++k)
                dp[i][j][k] = -10000000;
    
    dp[0][0][down] = cost[0];
    for (int i=1; i<m; ++i)
        dp[0][i][left] = max(dp[0][i-1][down], dp[0][i-1][left]) + cost[i];

    for (int i = 1; i<n; ++i)
    {
        ++cur_i;
        get_cost(m);
        int y = cur_i%2;
        int ry = (cur_i-1)%2;
            
        for (int j=0; j<m; ++j)
            dp[y][j][down] = max(dp[ry][j][down], max(dp[ry][j][left], dp[ry][j][right])) + cost[j];

        for (int j=1; j<m; ++j)
            dp[y][j][left] = max(dp[y][j-1][down], dp[y][j-1][left]) + cost[j];

        for (int j=m-2; j>-1; --j)
            dp[y][j][right] = max(dp[y][j+1][down], dp[y][j+1][right]) + cost[j];
    }
    
    cout<<max(dp[(cur_i%2)][m-1][down], dp[(cur_i%2)][m-1][left]);
    return 0;
}

---