문제
https://school.programmers.co.kr/learn/courses/30/lessons/12913
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
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
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 구현 / 스킬트리 (0) | 2025.10.16 |
|---|---|
| 프로그래머스 / 스택 / 택배상자 (0) | 2025.10.14 |
| 프로그래머스 / 해시 / [3차] 압축 (0) | 2025.10.12 |
| 프로그래머스 / 구현, 정수론 / k진수에서 소수 개수 구하기 (0) | 2025.10.11 |
| 프로그래머스 / 스택 / 뒤에 있는 큰 수 (0) | 2025.10.05 |