[TIL] 99클럽 코테 스터디 14일차 TIL + DP

🍀 오늘의 회고

오늘 오랜만에 친구를 만났다. 이력서/포트폴리오 이야기도 했는데, 포트폴리오에 앱의 기획적인 언급이 너무 적어서 어떤 앱인지 설명이 필요할 것 같다고 했다. 그리고 어떤 기능을 구현할 때 적용한 기술인지 언급할 필요도 있어 보인다고 했다. 그동안 이력서/포폴 피드백을 받은 적이 없었는데, 이제 점점 윤곽이 보이는 이 이력서를 피드백받으면서 업데이트해야 할 것 같다.

 

오늘은 약속 갔다가 다른 할 일을 거의 못했다. 내일도 일정이 있는데.. 밤에 잘 해야지..!

 

🌼 오늘의 문제 - 백준 17484. 진우의 달 여행 (Small)

처음에 DP를 고려했는데, 갔던 방향을 다시 고려할 방법이 떠오르지 않았다. DFS로도 풀 수 있다는데, 내일은 이 문제를 다시 풀어봐야겠다.

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]

# dp[i][j][k] → i행 j열까지 왔고, 이전 이동 방향이 k (0: 왼쪽, 1: 직진, 2: 오른쪽)
INF = float('inf')
dp = [[[INF] * 3 for _ in range(m)] for _ in range(n)]

# 첫 행은 이전 행이 없으므로 초기화
for j in range(m):
    for d in range(3):
        dp[0][j][d] = matrix[0][j]

for i in range(1, n):
    for j in range(m):
        # 왼쪽에서 오는 경우 (이전 방향: 오른쪽 X)
        if j > 0:
            dp[i][j][0] = min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2]) + matrix[i][j]
        # 위에서 오는 경우 (이전 방향: 왼쪽, 오른쪽 X)
        dp[i][j][1] = min(
            dp[i - 1][j][0] if j > 0 else INF,
            dp[i - 1][j][2] if j < m - 1 else INF
        ) + matrix[i][j]
        # 오른쪽에서 오는 경우 (이전 방향: 왼쪽 X)
        if j < m - 1:
            dp[i][j][2] = min(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + matrix[i][j]

# 마지막 행에서 최소값 찾기
result = INF
for j in range(m):
    for d in range(3):
        result = min(result, dp[n - 1][j][d])

print(result)