출처 | https://www.acmicpc.net/problem/1149

코드

# red, green, blue 3개 중 하나의 색으로 칠해야한다.
# case - 1
# --
#    - 

# case - 2
#   --
# -

# case - 2
# -  -
#  - 

# 3가지 경우에 대해서 나눠서 생각해야한다.
# 비용의 최솟값을 출력한다. -> min 함수 사용
# 1차원 배열이므로 값 자체를 받아야 한다. list 사용
import sys

input = sys.stdin.readline
n = int(input())
dp = [0] * (n)
for i in range(n): # 값 자체를 저장하는 곳 User Part
  dp[i] = list(map(int, input().split()))

for i in range(1, len(dp)):
  dp[i][0] = min(dp[i-1][1], dp[i-1][2])+dp[i][0] # case - 2번 경우
  dp[i][1] = min(dp[i-1][2],dp[i-1][0])+dp[i][1] # case - 3번 경우
  dp[i][2] = min(dp[i-1][0],dp[i-1][1]) + dp[i][2]

print(min(dp[i][0], dp[i][1], dp[i][2])) 

시간복잡도

• O(n)

자료구조

• List[]

핵심 아이디어

• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. -> Point

• Min를 통해서 최솟값을 구한다.