[백준] 17404 - RGB거리 2 🎨 (Python) / 골드 4 / DP

BAEKJOON Logo

 

Contents

 

---

1.  문제🔥

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

문제

문제를 요약하자면, 첫째줄에 집 개수 N이 주어집니다. 다음 줄부터는, 집을 R, G, B로 칠할 때 드는 비용이 주어집니다. 집은 빨강, 초록, 파랑 중 하나로만 칠해야 하며 아래 3가지 규칙을 만족하는 최소 비용을 출력해야합니다.

1. 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
2. N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
3. i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

 

1) 예제 입출력❄️

예제 입출력

첫 번째 예제를 보면 40 -> 57 -> 13 이렇게 선택했을 때, 최소비용 110이 나오는 것을 볼 수 있습니다.

 

2. 핵심 논리☢️

이 풀이에서 핵심 논리는, for문을 3번을 돌며 첫번째 for문에서는 첫 번째 집을 R로 칠했을 때의 최소비용을 dp테이블에 저장하고, 두번째는 첫 번째집을 G로 칠했을때의 최소비용 dp 테이블, 3번째는 첫 번째집을 B로 칠했을 때의 최소비용 dp테이블을 만드는 것입니다. 그리고 각 for문의 끝에서 dp테이블 중에 첫 번째 집과 마지막 집의 색이 다를 때만 비용을 보며, 최솟값을 갱신해 나갑니다.

 

3. 풀이 코드✅

1) 코드

N=int(input())
house_rgb=[list(map(int,input().split())) for _ in range(N)]
ans=I=1e9
for i in range(3):
    dp = [[I,I,I] for _ in range(N)]
    dp[0][i] = house_rgb[0][i]
    for j in range(1,N):
        dp[j][0] = house_rgb[j][0] + min(dp[j-1][1],dp[j-1][2])
        dp[j][1] = house_rgb[j][1] + min(dp[j-1][0],dp[j-1][2])
        dp[j][2] = house_rgb[j][2] + min(dp[j-1][0],dp[j-1][1])
    for k in range(3):
        if i != k:
            ans=min(ans,dp[-1][k])
print(ans)

N에 집의 개수를 입력받고, house_rgb에 각 집별로 RGB 색칠할 때의 비용을 입력받습니다. ans는 최소비용을 매우큰 값으로 초기화 해줍니다. I는 무한대의 개념으로 매우 큰값으로 초기화해줍니다. 이제 for문을 돌며 첫 번째집을 각각 R, G, B로 칠했을 때의 최소비용을 dp를 통해 구합니다. 각 for문 내부에서 dp 테이블을 길이가 3인 리스트가 N개 있는 이중 리스트로 초기화해줍니다. 첫번째 집을 색칠하고 그다음 집부터는 for문을 j로 돌며 집을 각각 R, G, B로 색칠했을 때의 최소비용을 갱신해 나갑니다. 그러면 dp의 마지막 값은 마지막 집을 R, G, B로 칠했을 때의 최소비용이 저장됩니다. 여기서 for문을 k로 돌며 첫 번째 집과 마지막 집의 색깔이 서로 다른 경우만 ans에 최솟값으로 갱신해 줍니다.

2) 주석 달린 코드

N=int(input())
house_rgb=[list(map(int,input().split())) for _ in range(N)]

ans=E=1e9
for i in range(3):
    dp=[[E, E, E] for _ in range(N)] # dp가 각 R, G, B로 시작했을 때
    dp[0][i] = house_rgb[0][i] # 처음 집 색칠
    for j in range(1,N): # 2번째 집부터 R, G, B로 색칠했을 때 최소값 갱신
        dp[j][0] = house_rgb[j][0] + min(dp[j-1][1], dp[j-1][2]) # 
        dp[j][1] = house_rgb[j][1] + min(dp[j-1][0], dp[j-1][2])
        dp[j][2] = house_rgb[j][2] + min(dp[j-1][0], dp[j-1][1])
    for c in range(3):
        if i != c: # 첫번째 집과 N번째 집이 다른 경우만 선택
            ans = min(ans,dp[-1][c])
print(ans)

 

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/17404_RGB%EA%B1%B0%EB%A6%AC_2.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/