본문 바로가기
Algorithm/프로그래머스

[프로그래머스] Lv2 - 땅따먹기 (파이썬)

by _temp 2022. 5. 14.

https://programmers.co.kr/learn/courses/30/lessons/12913

 

코딩테스트 연습 - 땅따먹기

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟

programmers.co.kr

 

def solution(land):
    N, M = len(land), len(land[0])
    dp = [[0 for _ in range(M)] for _ in range(N)]
    for j in range(M):
        dp[0][j] = land[0][j]
    for i in range(1, N):
        for j in range(M):
            dp[i][j] = max(dp[i-1][:j]+dp[i-1][j+1:])+land[i][j]
    return max(dp[-1])

 

DP
1. land를 이용해서 N과 M을 구하고 2차원 dp를 정의
2. dp의 맨 윗줄을 land값으로 초기화
3. dp
    - 이전 행에서 자신의 열을 제외한 dp리스트(슬라이싱 이용)에서 가장 큰 값과 자신의 값의 합을 dp에 초기화
4. dp의 마지막 행의 최댓값 출력