Algorithm/프로그래머스
[Python] 프로그래머스 Lv2 - 땅따먹기
떵호
2022. 6. 18. 16:56
728x90
🔗 문제링크
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr
📂 분류
DP
💡 풀이
처음에는 단순하게 행의 최댓값과 열이 겹친다면 두 번째로 큰 수를 구하는 방식으로 접근했다. 하지만 이 접근방식은 잘못된 방식이었고 이 문제는 DP로 접근해야 해결할 수 있는 문제였다.
접근방식
- 현재 값에 같은 열은 밟을 수 없으므로 현재 열을 제외한 이전 행의 최댓값을 더해준다.
💻 코드
def solution(land):
for i in range(1, len(land)):
for j in range(len(land[i])):
land[i][j] += max(land[i - 1][:j] + land[i - 1][j + 1:])
return max(land[-1])728x90