알고리즘(BOJ)/DP
백준 11048번 - 이동하기
Moon_Dev
2018. 1. 28. 18:45
https://www.acmicpc.net/problem/11048
N제한이 1000까지 있어서 입력받는 데만 O(N^2)의 시간이 걸린다.
dp를 통해서 문제를 해결해야 한다.
입력을 받을 때 마다 dp[i][j]의 값을 업데이트 해야 하는데
가져갈 수 있는 사탕의 최대값은 (i,j)의 사탕 개수에서
(i-1,j) / (i,j-1) / (i-1,j-1)의 사탕 개수의 최대값을 더해주면 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ int N,M; cin>>N>>M; vector<vector<int>> dp(N+1,vector<int>(M+1,0)); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){ scanf("%d",&dp[i][j]); dp[i][j]+=max(dp[i-1][j-1],max(dp[i-1][j],dp[i][j-1])); } cout<<dp[N][M]<<endl; return 0; } | cs |