[백준] 17404 RGB거리 2

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

이전에 사용한 색상과 다르게 선택해야하고, 가장 첫 집과 마지막 집의 색상이 달라야 하므로 인덱스로 색상을 관리하였습니다.

입력이 3가지 색상이므로 크기 9의 1차원 배열을 생성하였습니다.

 

0~2 인덱스는 빨간색으로 시작하는 경우로 각 인덱스는 빨간색, 초록색, 파란색으로 끝나는 경우들을 의미합니다.

3~5 와 6~8 인덱스는 각각 초록색과 파란색으로 마지막에 끝나는 경우는 위와 동일합니다.

2) 알고리즘

• 다이나믹 프로그래밍

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                                                       # 집의 개수
answer = 1e10                                                                       # 비용 (초기 최댓값)

# 색을 칠하는 비용을 기록하는 DP
# 0 ~ 2 인덱스 : 빨간색으로 시작해서 빨간색, 초록색, 파란색으로 끝나는 경우 
# 3 ~ 5 인덱스 : 초록색 시작
# 6 ~ 8 인덱스 : 파란색 시작

for i in range(N):                                              
    rgb = list(map(int, sys.stdin.readline().split()))                              # 색상을 입력 받음

    if not i:                                                                       # 첫 집일 경우
        dp = [1e10] * 9                                                             # 모든 경우 최댓값으로 설정
        for k in (0, 4, 8):                                                         # RGB 각 색상으로 시작하는 집은 비용 입력
            dp[k] = rgb[k%3]
    else:
        pre = dp[:]                                                                 # 이전까지 칠한 비용들 복사
        for k in range(9):                                                              
            dp[k] = rgb[k%3] + min(pre[(k+1)%3 + k//3*3], pre[(k+2)%3 + k//3*3])    # 현재 칠하려는 색상과 다른 색으로 칠한 이전 집들 중 작은 값을 더함

print(min(*dp[1:4], *dp[5:8]))              # 시작과 마지막에 같은 색인 경우 - 인덱스 1, 4, 8 을  제외한 값들 중 최솟값

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

처음 집과 마지막 집의 색상을 다르게 해야한다는 조건이 까다로웠습니다.

이 조건을 만족시키기 위해 나올 수 있는 모든 경우들을 다루었으나 시간과 메모리 초과 문제가 발생했습니다.

 

더 빠른 시간과 적은 메모리 사용을 위해 배열의 크기를 줄이고 기억하는 이전 기록도 줄여야 했습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

17404번: RGB거리 2

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다