[BOJ] #2169 로봇 조종하기

시간 제한	메모리 제한	정답 비율
2 초	512 MB	31.977%

 

2169번: 로봇 조종하기

 

방법

로봇이 '아래와 오른쪽'으로 가는 것과 '아래와 왼쪽'으로 가는 것 두 방법을 각각 구해서 더 큰 값으로 dp 배열을 채워나간다.

역시나.. dp는 통찰력!! 통찰력을 키우자ㅜㅜ

 

메모리	시간
9012 KB	124 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF -1000000
int arr[1005][1005];
int dp1[1005][1005];
int dp2[1005];
int n, m;
int main(void)
{
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp1[i][j] = INF;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &arr[i][j]);
 
    dp1[1][0] = 0;
    for (int j = 1; j <= m; j++)
        dp1[1][j] = dp1[1][j - 1] + arr[1][j];
 
    for (int i = 2; i <= n; i++) {
 
        for (int j = 0; j <= m+1; j++)
            dp2[j] = INF;
 
        for (int j = 1; j <= m; j++) {
            dp1[i][j] = max(dp1[i][j - 1], dp1[i - 1][j]) + arr[i][j];
        }
        for (int j = m; j >= 1; j--) {
            dp2[j] = max(dp2[j + 1], dp1[i - 1][j]) + arr[i][j];
        }
 
        for (int j = 1; j <= m; j++) {
            dp1[i][j] = max(dp1[i][j], dp2[j]);
        }
    }
 
    printf("%d\n", dp1[n][m]);
    return 0;
}

 

1차원 배열 3개로 끝내는 방법!

맞은 사람 코드를 보면서 또 한 번 배우게 된다.. 멋진 사람들

이 방법은 가중치를 받으면서 동시에 연산을 하는데, 배열 B 가 '아래와 오른쪽'으로 이동하는 가중치의 합, A가 '아래와 왼쪽'으로 이동할때의 가중치가 된다.

메모리	시간
1128 KB	116 ms

#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[1000], A[1000], B[1000];
int n, m;
int main(void){    
    scanf("%d%d", &n, &m);
    fill(dp + 1, dp + m, (int)-1e9);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &A[j]);
            B[j] = (j && B[j - 1] > dp[j] ? B[j - 1] : dp[j]) + A[j];
        }
        for (int j = m - 1; j >= 0; j--)
            A[j] += j<m - 1 && A[j + 1]>dp[j] ? A[j + 1] : dp[j];
        for (int j = 0; j < m; j++)
            dp[j] = max(A[j], B[j]);
    }
    printf("%d", dp[m - 1]);
    
    return 0;
}