17404. [Python]RGB거리 2

1. 문제

 

https://www.acmicpc.net/problem/17404

 

2. 접근 방법

 

• 시간 제한: 0.5초
• 메모리 제한: 128MB
• DP

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

N = int(input())

houses = []
# 최소값 저장 변수
result = 10**9
# 집 마다 색에 대한 값
for _ in range(N):
    houses.append(list(map(int,input().split())))
# 빨, 파, 초 선택하는 범위
for i in range(3):
    # dp 값 각각 0번 집 어느 색을 선택한지에 대한 초기화
    dp = [[10**9] * 3 for _ in range(N)]
    # dp 첫 인덱스 값 갱신
    dp[0][i] = houses[0][i]
    # N번 DP 까지 값 갱신
    for j in range(1,N):
        dp[j][0] = min(dp[j-1][1],dp[j-1][2]) + houses[j][0]
        dp[j][1] = min(dp[j-1][0],dp[j-1][2]) + houses[j][1]
        dp[j][2] = min(dp[j-1][0],dp[j-1][1]) + houses[j][2]
    # 결과값 출력할 반복문 => i번 인덱스와 N 번인덱스는 같으면 안되기 때문에 결과값에서 제외
    for k in range(3):
        if k != i:
            result = min(result,dp[N-1][k])
print(result)

 

4. 문제를 풀고난 후 생각

 

• 모든 집에 대해서 DP를 실행할 생각을 못하고 있었다. 고민을 1시간정도 한 후 질문 게시판의 질문을 읽어보며 문제에 접근방법을 깨달았다.
• 첫 집에 대해서 R,G,B 각각 인덱스를 초기값으로 선언해준 후 그 값으로 이후 모든 DP를 채워나가는 방식으로 문제를 해결했다.
• 문제의 조건인 N번 집의 경우 N-1 과 1 번 집이랑 색이 같으면 안되는거 아닌가? 라는 질문에 대해서는 result 값을 갱신하는 과정에서 i 번째 색( 처음 집을 색칠한 색 ) 을 제외하고 min 값을 구해주는 것으로 해결할 수 있었다.
• DP를 접근하는 방식에 있어서 아직 많이 미흡한 점이 있고 이를 보완하기 위해 꾸준히 접근하는 것 밖에 없을 것 같다.... ㅜㅜ

 

5. 문제를 푸는데 도움이 되는 지식

 

• DP