Tech Log 🛠️

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

              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]))
    
    

접근방법 ) 먼저 3까지의 합은 그리 어렵지 않기에 배열로 설정해주었다.

              그 다음 4부터 합들을 나열하였는데 앞이 1이오는 경우 , 2가 오는경우 , 3이오는 경우 이런식으로 경우를 나                누었다.

              1+1+1+1

              1+2+1

              1+1+2

              1+3

              이렇게 1의 경우만 살펴보면 1 + 3의 의미를 가진다는 것을 알수 있다. 이는 곧 1+d[2] 를 의미하며 2,3의 경

              우도 동일한 방식으로 계산하였더니 7의 가짓수를 얻을 수 있었다.

              따라서 점화식은 d[i] = d[i-1]+ d[i-2]+d[i-3] 임을 알 수 있다.

-----------------------

n = int(input())

접근방법

-바텀 업 방식으로 진행하였다.

 2 ,3 으로 나누어 떨어지는 지 확인 한 후에 이를 -1 을 한 경우와 비교해 더 작은 수를 배열에 넣어주었디.