프로그래머스. 땅따먹기

dhttps://programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

 

문제를 보고 처음에 백트래킹을 이용한 문제, N-Queen과 유사한 문제라고 생각하고 풀었는데 풀다보니까 

하나의 열에 한번만 갈수 있는게 아닌 같은 열을 연속으로 갈수 없는 것이었고 결과적으로 백트래킹 문제가 아니었다.

(행 길이가 10만이어서 시간도 오래걸린다)

 

다시 처음부터 보니까 dp문제 였다.

첫 행부터 각 열에 도달할수 있는 최댓값을 축척해나가면 된다.

 

주어진 input이 다음과 같다면

다음과 같이 값을 축척해 나간다