[문제 링크]




DP문제이다. 어려운 문제는 아니고, 다음으로 선택할 수 있는 경로의 경우만 알면 쉽게 풀리는 문제인 것 같다.

자신을 기준으로 상하좌우는 접근할 수 없기 때문에, 대각선에 위치한 스티커나, 대각선에서 오른쪽으로 한칸 옆에 있는 스티커를 다음 경로로 선택하면 된다.

이렇게 모든 점수들을 더한 값 중 최대값을 구하면 되었다.

밑은 이를 구현한 코드이다.



#include <cstdio> #include <cstring> #include <algorithm> int t,n,arr[2][100000],cache[2][100000]; int relPos[4][2] = {{1,1},{1,-1},{2,-1},{2,1}}; int dp(int y, int x){ //기저사례 : y 끝에 도달했을 때 if(x==n-1) return arr[y][x]; int& ret = cache[y][x]; if(ret!=-1) return ret; ret = 0; for(int i=0;i<4;i++){ int px = x + relPos[i][0]; int py = y + relPos[i][1]; //스티커 범위를 초과하지 않으면 if(px<n&&px>=0&&py<2&&py>=0){ //최대값 구하기, 기존 ret와, 이 값+ 현재 좌표값 ret = std::max(ret,dp(py,px)+arr[y][x]); } } return ret; } int main(){ scanf("%d",&t); while(t--){ memset(cache,-1,sizeof(cache)); scanf("%d",&n); for(int y=0;y<2;y++){ for(int x=0;x<n;x++){ scanf("%d",&arr[y][x]); } } //(0,0)으로 시작할 때랑, (1,0)으로 시작할때 중 최댓값을 구하여 출력한다. printf("%d\n",std::max(dp(0,0),dp(1,0))); } }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10799 쇠막대기  (2) 2016.03.28
백준 - 1520 내리막 길  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07

+ Recent posts