728x90
반응형
코딩테스트 연습 - 땅따먹기
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟
programmers.co.kr
👩🏻💻 코드
def solution(land):
dp = [[0] * 4 for _ in range(len(land))]
for i in range(len(land)):
for j in range(4):
if i == 0:
dp[i][j] = land[i][j]
else:
max_list = dp[i - 1].copy()
del max_list[j]
dp[i][j] = max(max_list) + land[i][j]
return max(dp[-1])
📝 정리
Dynamic Programming을 이용해 풀었다.
연속해서 같은 열을 밟을 수 없기 때문에, 이전의 밟은 값을 제외한 리스트에서 max 값을 구하여 dp에 저장하였다. 그리고 마지막 행에서 max 값을 구하여 리턴하였다.
728x90
반응형