문제 링크
https://programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr
풀이
- dp 문제
1행은 다른 땅을 밟고 도착하지 않으므로 2행부터 시작
2행부터 전 행에서 자기 자신과 같은 열을 제외한 다른 열의 최댓값 더하기
계속 누적되어 마지막 행의 최댓값이 정답이 된다.
def solution(land):
n = len(land)
for i in range(1, n):
for j in range(4):
# i-1 행의 0열을 제외한 다른 열의 최댓값 더하기
if j == 0 :
land[i][j] += max(land[i-1][1:])
# i-1 행의 1열을 제외한 다른 열의 최댓값 더하기
if j == 1 :
land[i][j] += max(max(land[i-1][2:]),land[i-1][0])
# i-1 행의 2열을 제외한 다른 열의 최댓값 더하기
if j == 2 :
land[i][j] += max(max(land[i-1][:2]),land[i-1][3])
# i-1 행의 3열을 제외한 다른 열의 최댓값 더하기
if j == 3:
land[i][j] += max(land[i-1][:-1])
# 마지막 행의 최댓값
return max(land[-1])
'개발 > algorithm' 카테고리의 다른 글
[프로그래머스][level2] 숫자의 표현 - python (0) | 2022.04.08 |
---|---|
[백준 5014번] 스타트링크 - python (0) | 2022.04.08 |
[프로그래머스][level2] n^2 배열 자르기 -python (0) | 2022.03.30 |
[프로그래머스][level2] 수식 최대화 -python (0) | 2022.03.30 |
[프로그래머스][level2] JandenCase 문자열 만들기 - python (0) | 2022.03.29 |