[BOJ] 백준 11048번: 이동하기

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

11048번: 이동하기

 

백준 난이도 실버 2의 기본적인 dp 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

int N, M, board[1001][1001], dp[1001][1001];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	
	for(int i = 1; i <= N; ++i){
		for(int j = 1; j <= M; ++j){
			cin >> board[i][j];
		}
	}
	
	for(int i = 1; i <= N; ++i){
		for(int j = 1; j <= M; ++j){
			dp[i][j] = max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1])) + board[i][j];
		}
	}
	
	cout << dp[N][M];
}

 

dp문제는 항상 그래왔듯 1) table 정의, 2) 점화식 찾기, 3) 초기값 설정의 3단계로 풀이합니다.

 

1) table 정의

dp[i][j] : (i, j)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값

 

2) 점화식 찾기

dp[i][j] = max(dp[i-1][j-1], max(dp[i-1][j], dp[i][j-1])) + board[i][j];

 

3) 초기값 설정

1-based index로 i = 0, j = 0 부분이 경계치 역할을 하여 초기값 설정이 불필요합니다.