백준 1149번 )RGB거리

접근방법) 다음 집의 관점에서 각각 색깔의 비용을 계산하여 최소 비용을 비교하는 관점으로 문제를 해결하였다.

              ex) 2번째 집의 파란색, min(첫번째집의 빨강 , 초록)

             이렇게 각각의 경우를 비교하여 올라가는 바텀 업 방식으로 알고리즘을 구성하였다.

 

소스코드

n = int(input())
d = [[0] * 3 for _ in range(n)]
min_list = [[0] * 3 for _ in range(n)]
for i in range(n):
    i1,i2,i3 = map(int,input().split())
    d[i][0] = i1
    d[i][1] = i2
    d[i][2] = i3

for i in range(n):
    if i ==0:
        min_list[i][0] = d[0][0]
        min_list[i][1] = d[0][1]
        min_list[i][2] = d[0][2]
    else:
        min_list[i][0] += d[i][0] + min(min_list[i-1][1],min_list[i-1][2])
        min_list[i][1] += d[i][1] + min(min_list[i-1][0],min_list[i-1][2])
        min_list[i][2] += d[i][2] + min(min_list[i-1][0],min_list[i-1][1])
        

print(min(min_list[n-1][0],min_list[n-1][1],min_list[n-1][2]))
----------------

처음에는 집,색깔 배열과 똑같은 배열을 만들어서 각각의 비용을 넣어주는 방식으로 하였다.

하지만 생각해보니 이미 만들어진 배열에 넣어도 상관이 없어서 아래 코드로 다시 구성하였다.

    

n = int(input())
d = [[0] * 3 for _ in range(n)]

for i in range(n):
    i1,i2,i3 = map(int,input().split())
    d[i][0] = i1
    d[i][1] = i2
    d[i][2] = i3

for i in range(1,n):
        d[i][0] = d[i][0] + min(d[i-1][1],d[i-1][2])
        d[i][1] = d[i][1] + min(d[i-1][0],d[i-1][2])
        d[i][2] = d[i][2] + min(d[i-1][0],d[i-1][1])
        

print(min(d[n-1][0],d[n-1][1],d[n-1][2]))