코딩테스트/프로그래머스
[프로그래머스] Level 2 - 땅따먹기 (Python)
ye0nn
2022. 6. 28. 14:32
https://programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr
✅ Solution
- dp를 이용하여 문제를 해결했다.
- 행을 하나씩 늘려가며 각 열마다 가질 수 있는 최댓값을 할당했다.
- 예를 들어, 2행 1열까지 오는 최댓값은 1행 2열, 1행 3열, 1행 4열의 최댓값 + 2행 1열의 값이다.
- 예를 들어, 2행 2열까지 오는 최댓값은 1행 1열, 1행 3열, 1행 4열의 최댓값 + 2행 2열의 값이다.
- 이를 이용해서 가장 마지막 행까지 구하고 마지막행에서의 최댓값을 리턴해준다.
✅ Code
def solution(land):
for i in range(1, len(land)):
land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3])
land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3])
land[i][2] += max(land[i-1][0], land[i-1][1], land[i-1][3])
land[i][3] += max(land[i-1][0], land[i-1][1], land[i-1][2])
return max(land[-1])