[파이썬] 땅따먹기

문제 설명

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

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

 

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

 

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

 

 

 

🎨 나의 풀이

def solution(land):
    dp=[[0]*4 for _ in range(100001)]
    dp[0]=land[0]
    row=len(land)
    
    for i in range(1, row) :
        for j in range(4) :
            for k in range(4) :
                if j != k :
                    dp[i][j]=max(dp[i-1][k] + land[i][j], dp[i][j])
    
    return max(max(*dp))

DP

k는 위쪽 땅, j가 아래 땅

어떤 땅k에서 j로 내려왔을 때가 더 큰지를 dp[i][j]에 담기

dp[i][j]=max(land[i][j]를 밟는 경우, land[i][j]를 밟지 않는 경우)

max(*dp)는 dp에서 가장 큰 행을 추출

max(max(*dp))는 가장 큰 행에서 가장 큰 수를 추출

주의할 점은 max(dp[row-1])이 아니다.

가장 마지막 행이 크다는 보장이 없기 때문이다.

 

 

import itertools
def solution(land):
    dp=[[0]*4 for _ in range(100001)]
    _len=len(land)
    for i in range(4) :     # 0행 값 입력
        dp[0][i]=land[0][i]

    for i in range(_len) :      # 행
        for j in range(4) :     # 열
            for k in range(4) :     # 4가지 선택지
                if j != k :         # 같은 열 피함
                    dp[i][j]=max(dp[i][j], land[i][j]+dp[i-1][k])   # 편의상 아래에서 위로 올라가게.

    return max(itertools.chain(*dp))

동적 계획법 풀이.

입력 행의 개수 100,000 이하에 맞춰서 dp리스트 만들었음.

아래에서 위 또는 위에서 아래 방향으로 계산 결과는 똑같다.

마지막에 chain으로 1차원 리스트로 풀어주고 max 값을 구했다.

 

 

✨ 다른 사람 풀이

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

for j in range(4)로 해도 됨

j를 밟으면 위에서는 j를 제외하고 큰 값을 찾는다. (슬라이싱)

 

 

문제 출처 👉 프로그래머스