문제
접근 방법
다아나믹프로그램을 활용해서 문제를 해결할 수 있다. 먼저 조건을 보면 이동하는 경우는 총 3가지로 오른쪽, 아래, 대각선 방향으로 이동이 가능하다.
가장 위쪽 행과 가장 왼쪽 열은 이전 사탕의 갯수를 그대로 더하고 나머지 가운데 부분은 접근 가능한 방향에서의 최대값을 가지는 식으로 코드를 작성했다.
- 가장 위쪽
dp[i][j] = map[i][j] + dp[i][j-1]; - 가장 왼쪽
dp[i][j] = map[i][j] + dp[i-1][j]; - 나머지 영역
dp[i][j] = map[i][j] + max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1]));
코드
#include <iostream> #include <algorithm> using namespace std; int N, M; int map[1000][1000]; int dp[1000][1000]; int main() { cin >> N >> M; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j ++) { cin >> map[i][j]; } } dp[0][0] = map[0][0]; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j ++) { // 가장 위쪽 if(i == 0 && j - 1 >= 0) { dp[i][j] = map[i][j] + dp[i][j-1]; } // 가장 왼쪽 if(j == 0 && i - 1 >= 0) { dp[i][j] = map[i][j] + dp[i-1][j]; } // 나머지 영역 if(i != 0 && j != 0) { dp[i][j] = map[i][j] + max(dp[i-1][j], max(dp[i][j-1], dp[i-1][j-1])); } } } cout << dp[N-1][M-1]; return 0; }