[파이썬] 백준 17404 RGB2

우선은 product 를 이용했고 예상했다시피 메모리 초과가 나왔다. 구글링을 통해 보니, 첫 집의 나머지 두개를 최댓값으로 변경해주는 방식으로 해결할 수 있었고, 이를 이요해서 풀었다.

import sys
from collections import deque
from itertools import product
import copy
 
 
num = int(input())
 
ks = [ ]
 
for i in range(num):
    ks.append(list(map(int,sys.stdin.readline().split(" "))))
 
 
'''
a = [0,1,2]
 
m = list(product(a,repeat=num))
 
index = [ ] 
 
def check(k):
 
    if k[0]==k[-1]:
        return False
 
    for i in range(0,len(k)-1):
        if k[i]==k[i+1]:
            return False
    return True
 
def find(k,temp):
    answers = 0
 
    for i in range(0,len(temp)):
 
        answers+=k[i][temp[i]]
 
    return answers
 
 
answer = [ ]
 
for i in range(0,len(m)):
    if check(list(m[i]))== True:
 
        answers = 0
 
        answer.append((find(k,list(m[i]))))
 
 
 
print(min(answer))
 
'''
answer = [ ]
 
k = copy.deepcopy(ks)
 
k[0][1] = 1000000000
k[0][2] = 1000000000
 
 
for i in range(1,len(k)):
 
    k[i][0] += min(k[i-1][1],k[i-1][2])
    k[i][1] += min(k[i-1][0],k[i-1][2])
    k[i][2] += min(k[i-1][0],k[i-1][1])
 
answer.append(min(k[-1][1],k[-1][2]))    
 
 
k1 = copy.deepcopy(ks)
 
k1[0][0] = 1000000000
k1[0][2] = 1000000000
 
 
for i in range(1,len(k1)):
 
    k1[i][0] += min(k1[i-1][1],k1[i-1][2])
    k1[i][1] += min(k1[i-1][0],k1[i-1][2])
    k1[i][2] += min(k1[i-1][0],k1[i-1][1])
 
answer.append(min(k1[-1][0],k1[-1][2]))           
 
k2 = copy.deepcopy(ks)
 
k2[0][0] = 1000000000
k2[0][1] = 1000000000
 
 
for i in range(1,len(k2)):
 
    k2[i][0] += min(k2[i-1][1],k2[i-1][2])
    k2[i][1] += min(k2[i-1][0],k2[i-1][2])
    k2[i][2] += min(k2[i-1][0],k2[i-1][1])
 
answer.append(min(k2[-1][0],k2[-1][1]))  
 
print(min(answer))