[백준] 17404번: RGB거리 2

스스로 푼 문제: O
걸린 시간: 52분

문제

풀이

1번째 집과 N번째 집의 색이 달라야한다는 조건을 어떻게 처리할지가 문제였다.

질문 게시판에서 1번째 집 색 별로 경우를 나눠서 해보라는 힌트를 보고 풀 수 있었다.

1번째 집의 색에 따라서 N번째 집 색으로 가능한 경우의 수가 달라지니까 이 부분은 경우를 나눠서 진행해야하나보다.

DFS로 풀 경우 경우의 수가 $3×2^{(N-1)}$개 발생하는데 2 ≤ N ≤ 1,000 조건 떄문에 최악의 경우에는 시간 초과가 발생할 수 있다.

이런 경우에는 DP로 풀이하는 방향으로 생각해보자.

코드

import sys

input = sys.stdin.readline

n = int(input()) # 집의 개수

house_costs = []
for _ in range(n):
  house_costs.append(list(map(int, input().split())))

ans = sys.maxsize
for c in range(3):
  total_costs = []
  if c == 0: # 첫번째 집이 R일 때
    total_costs.append((house_costs[0][0], sys.maxsize, sys.maxsize))
  elif c == 1: # 첫번째 집이 G일 때
    total_costs.append((sys.maxsize, house_costs[0][1], sys.maxsize))
  else: # 첫번째 집이 B일 때
    total_costs.append((sys.maxsize, sys.maxsize, house_costs[0][2]))
  
  for i in range(1, n):
    R_cost = min(total_costs[i-1][1], total_costs[i-1][2]) + house_costs[i][0]
    G_cost = min(total_costs[i-1][0], total_costs[i-1][2]) + house_costs[i][1]
    B_cost = min(total_costs[i-1][0], total_costs[i-1][1]) + house_costs[i][2]

    total_costs.append([R_cost, G_cost, B_cost])

  if  c == 0: # 첫번째 집이 R일 때
    ans = min(ans, total_costs[-1][1], total_costs[-1][2])
  elif c == 1: # 첫번째 집이 G일 때
    ans = min(ans, total_costs[-1][0], total_costs[-1][2])
  else: # 첫번째 집이 B일 때
    ans = min(ans, total_costs[-1][0], total_costs[-1][1])

print(ans)

정리

• DFS로 풀 경우 경우의 수가 너무 커지면 DP로 푸는 것을 고려해보기