[C++] 백준 11048번 : 이동하기 (S1)

#문제

www.acmicpc.net/problem/11048

11048번: 이동하기

 

#풀이 & 학습한 내용

opti[i][j]를 (i,j)위치까지 얻을 수 있는 최대 candy수로 두고, bottom up방식을 통해 table을 하나씩 채워나간다. 이때, opti[i][j]에서 필요한 정보는 왼쪽과 위쪽 정보이기 때문에 이를 고려하여 for문을 구성한다. 나는 테이블에 넣는 basis를 아래로만 가는 경우, 오른쪽으로만 가는 경우에 대해서 채워주고 table의 다른 요소들을 채웠다. 하지만 사용되지 않는 index가 0인 부분을 활용하면, 전역배열로 선언하면 0으로 초기화되고 내가 넣어준 basis가 없어도 for문의 결과에 문제가 생기지 않았다. 0은 더하나 안더하나 똑같기 때문이다. 이런 부분은 다른 문제에서 충분히 응용될 것 같다.

 

#소스코드

#include<iostream>
 
#define max(a,b) (((a) > (b)) ? (a) : (b))
using namespace std;
 
int candy[1002][1002];//input으로 들어오는 candy수를 저장할 배열
int opti[1002][1002];//opti[i][j]는 i,j까지 얻을 수 있는 최대 캔디수
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> candy[i][j];
        }
    }
 
    opti[1][1] = candy[1][1];
    
    for (int i = 1; i <= N; i++) {
        opti[i][1] = opti[i - 1][1] + candy[i][1];
    }//table에서 아래로만 가는 경우인 basis 넣기
    
    for (int j = 1; j <= M; j++) {
        opti[1][j] = opti[1][j-1] + candy[1][j];
    }//table에서 오른쪽으로만 가는 경우인 basis 넣기
 
    for (int i = 2; i <= N; i++) {
        for (int j = 2; j <= M; j++) {
            opti[i][j] = max(opti[i - 1][j], opti[i][j - 1]) + candy[i][j];
        }
    }//opti[i][j]는 i,j까지 얻을 수 있는 최대 캔디수
 
    cout << opti[N][M] << "\n";
}

<개선된 풀이(전역으로 선언된 배열이 0으로 초기화된다는 점을 이용: 0은 더해져도 상관없다)>

#include <iostream>
#include <algorithm>
#define max(a,b) (((a) > (b)) ? (a) : (b))
using namespace std;
 
int DP[1002][1002];
int N, M;
 
int main() {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> DP[i][j];
 
            DP[i][j] += max(DP[i - 1][j], max(DP[i - 1][j - 1], DP[i][j - 1]));
        }
    }
 
    cout << DP[N][M] << '\n';
 
    return 0;
}