프로그래머스 / DP / 땅따먹기

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

N행에 4열에 같은 열을 연속해서 밟지 않고 최고점을 얻는다고 할 때 몇 점인지 알아내는 문제이다.

 

X행 Y열에 도착했을 때 얻을 수 있는 최고점이라고 DP 테이블을 정의하고 풀이를 진행하면 된다.

 

필자는 DP를 재귀방식으로 구현하였다.

매개변수는 행(row), 열(col), 경계면(boundary)을 넣어주었다.

 

DP의 로직은

1. 현재 행이 경계면에 도착했는지 

2. 현재 행, 열에 도착한 적이 있었는지

3. 아니라면 열과 다른 곳으로만 갈 수 있게끔 for문을 돌 수 있게 해주었다.

 

 

정답코드

---

'''
'25. 10. 13.(월)

1. N행 4열 
2. 같은 열을 연속해서 밟을 수 없다.
3. 최고점을 얻어내야 한다.

DP이다.
'''
import sys
sys.setrecursionlimit(120000)
dp = [[-1] * 5 for _ in range(100002)]
board = []
def down(row: int, col: int, boundary: int) -> int:
    global dp, board
    if row == boundary:
        return 0
    if dp[row][col]!=-1:
        return dp[row][col]
    dp[row][col] = 0
    #4개의 열 중 col과 다른 곳으로만 가야 함.
    for target in range(4):
        if col == target:continue
        dp[row][col] = max(dp[row][col], down(row + 1, target, boundary) + board[row][col])
    
    return dp[row][col]

def solution(land):
    global board
    answer = 0
    for row in land:
        board.append(row[::])
    # print(board)
    for i in range(4):
        answer = max(answer, down(0, i, len(land)))
    return answer

 

깃허브 : https://buly.kr/4mdalWh

유튜브 : https://youtu.be/rlBC6yRXXdc