프로그래머스 땅따먹기

[프로그래머스] 땅따먹기 - 자바스크립트

문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이 처음에는 DFS로 접근했다. N회까지 재귀를 돌면서, X행에서는 X-1행에서 선택하지 않은 열을 선택하여 더했다. 각각의 경우의 수로부터 N행까지 도달했을 때, 최댓값일 경우 최댓값을 갱신하도록 했다. 물론 주어진 행 N이 최대 100,000이기 때문에 재귀 호출로 인한 시간초과 이슈가 발생했다. 모든 경우의 수를 조회할 수 없다면, DP(동적 계획법)를 생각해봐야 한다. 풀이방법 DP답게 생각해보자. land 행렬은 N x 4 크..