[TIL]24-12-30

https://www.acmicpc.net/problem/1149
이 문제를 (답보고) 풀었다..

그러나 dp문제인것을 파악한것.
dp의 크기를 옳게 정의하고
점화식을 세우려 시도한 것은 잘 한거같다..
점화식도 하나의 완벽한 식으로 무조건 나와야 하는 줄 알았는데
이 문제의 해답을 보고 꼭 그렇지만은 않아도 되는구나 라는 걸 배웠다.

점화식은 i 번째 집을 j가지 색으로 칠 했을 때로 가정하고 세우면 되는데
어차피 RGB 세가지 색으로 제한이 되어있기 때문에 이중 포문으로 할 필요가 없다.

K = int(input())
arr = [list(map(int, input().split())) for _ in range(K)]

dp = [[0]*3 for _ in range(K)]

dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

for i in range(1, K):
    dp[i][0] = arr[i][0]+min(dp[i-1][1], dp[i-1][2])
    dp[i][1] = arr[i][1]+min(dp[i-1][0], dp[i-1][2])
    dp[i][2] = arr[i][2]+min(dp[i-1][0], dp[i-1][1])

result = min(dp[K-1][0], dp[K-1][1], dp[K-1][2])
print(result)




import sys
input = sys.stdin.readline


N = int(input())
cost = [list(map(int, input().split())) for _ in range(N)]

# 초기값 설정
prev = cost[0][:]  # 첫 번째 집의 비용 초기화

# DP 계산
for i in range(1, N):
    curr = [0] * 3  # 현재 집의 비용을 저장
    curr[0] = cost[i][0] + min(prev[1], prev[2])  # 빨강으로 칠할 때 최소 비용
    curr[1] = cost[i][1] + min(prev[0], prev[2])  # 초록으로 칠할 때 최소 비용
    curr[2] = cost[i][2] + min(prev[0], prev[1])  # 파랑으로 칠할 때 최소 비용
    prev = curr  # 현재 값을 이전 값으로 업데이트

# 최종 최소 비용
result = min(prev)
print(result)

이건 gpt가 알려준 방법인데 1차원 배열만을 써서 구하는 방법이다.
공간복잡도가 O(n)에서 O(1)로 감소한다.

라고 했는데 실제로 제출을 해보니 메모리는 딱히 차이가 나지 않았다(????)