πŸ“ BOJ - RGB거리

문제

BOJ 1149번 : RGB거리

μ ‘κ·Ό 방법

일련의 NN개의 집이 μ£Όμ–΄μ‘Œμ„ λ•Œ, λ‹€μŒμ˜ κ·œμΉ™μ„ 가지고 μΉ ν•  λ•Œ μ΅œμ†Œ λΉ„μš©μ„ κ΅¬ν•˜λŠ” λ¬Έμ œμ΄λ‹€.

  • 11번 μ§‘μ˜ 색은 22번 μ§‘μ˜ 색과 같지 μ•Šμ•„μ•Ό ν•œλ‹€.
  • NN번 μ§‘μ˜ 색은 Nβˆ’1N-1번 μ§‘μ˜ 색과 같지 μ•Šμ•„μ•Ό ν•œλ‹€.
  • ii(2≀i≀Nβˆ’12 ≀ i ≀ N-1)번 μ§‘μ˜ 색은 iβˆ’1i-1번, i+1i+1번 μ§‘μ˜ 색과 같지 μ•Šμ•„μ•Ό ν•œλ‹€.

μ„€λͺ…

λ™μ κ³„νšλ²•μ—μ„œ κ°€μž₯ μ€‘μš”ν•œ 것은 ν˜„μž¬μ— μ§‘μ€‘ν•˜λŠ” 것이닀. 이 λ¬Έμ œμ—μ„œλŠ” ii번째 집을 μ–΄λ–»κ²Œ 칠할지 κ²°μ •ν•˜κΈ° μœ„ν•΄μ„œλŠ” iβˆ’1i-1번째 μ§‘μ˜ 색을 ν”Όν•˜λ©΄ λœλ‹€!

예λ₯Ό λ“€λ©΄, μ„Έ 번째 집을 λΉ¨κ°„μƒ‰μœΌλ‘œ μΉ ν•œλ‹€κ³  ν•  λ•Œ 두 번째 집을 μ΄ˆλ‘μƒ‰, νŒŒλž€μƒ‰μœΌλ‘œ μΉ ν–ˆμ„ λ•Œ 쀑 κ°€μž₯ μ €λ ΄ν•œ λΉ„μš©μ— μ„Έ 번째 집을 λΉ¨κ°„μƒ‰μœΌλ‘œ μΉ ν•  λ•Œμ˜ λΉ„μš©μ„ 더해주면 λœλ‹€. 그럼 계속 μ΅œμ†Œ λΉ„μš©μ„ μœ μ§€ν•œ μ±„λ‘œ μΉ ν•  수 μžˆλ‹€. 문제의 μ˜ˆμ‹œλ‘œ ν‘œλ₯Ό 그리면 λ‹€μŒκ³Ό κ°™λ‹€.

rgb-table

κ²°λ‘ 

NN개의 집을 μΉ ν•˜λŠ” 것도 λ™μΌν•˜λ‹€. μ•žμ˜ μ§‘μ˜ 각 μƒ‰μ˜ λΉ„μš©μ„ 보고 μ§€κΈˆ μΉ ν•˜λ €λŠ” 색을 μ œμ™Έν•œ 색 쀑 μ΅œμ†Œ λΉ„μš©μ„ 계산해 ν˜„μž¬ μΉ ν•˜λ €λŠ” μƒ‰μ˜ λΉ„μš©μ„ λ”ν•΄μ£ΌκΈ°λ§Œ ν•˜λ©΄ λœλ‹€. 그럼 λ‹€μŒκ³Ό 같은 점화식이 λ„μΆœλœλ‹€. μ΄λ ‡κ²Œ κ΅¬ν•œ κ°’ 쀑 rgb[N]rgb[N]의 μ—¬λŸ¬ κ°’ 쀑 μ΅œμ†Œκ°’μ΄ λͺ¨λ“  집을 μΉ ν•  λ•Œ λ“œλŠ” μ΅œμ†Œ λΉ„μš©μ΄λ‹€!

rgb[i][r]=cost[i][r]+min(rgb[iβˆ’1][g],rgb[iβˆ’1][b])rgb[i][r] = cost[i][r] + min(rgb[i-1][g], rgb[i-1][b]) rgb[i][g]=cost[i][g]+min(rgb[iβˆ’1][r],rgb[iβˆ’1][b])rgb[i][g] = cost[i][g] + min(rgb[i-1][r], rgb[i-1][b]) rgb[i][b]=cost[i][b]+min(rgb[iβˆ’1][r],rgb[iβˆ’1][g])rgb[i][b] = cost[i][b] + min(rgb[i-1][r], rgb[i-1][g])
  • cost[r]cost[r] : i번째 μ§‘μ˜ 빨간색을 μΉ ν•  λ•Œμ˜ λΉ„μš©
  • rgb[i][r]rgb[i][r] : i번째 집을 λΉ¨κ°„μƒ‰μœΌλ‘œ μΉ ν•  λ•Œμ˜ ν˜„μž¬κΉŒμ§€μ˜ μ΅œμ†Œ λΉ„μš©

κ΅ν›ˆ

λ™μ κ³„νšλ²•μ€ ν˜„μž¬λ₯Ό κΈ°μ€€μœΌλ‘œ κ³Όκ±°λ₯Ό μΆ”μΈ‘ν•˜λŠ” 것이닀. 이 λ¬Έμ œμ—μ„œλ„ λ‚΄κ°€ 이 집을 빨간색을 칠할지, νŒŒλž€μƒ‰μ„ μΉ ν• μ§€λŠ” λͺ¨λ₯Έλ‹€! λ‹€λ§Œ λ‚΄κ°€ 빨간색을 μΉ ν•œλ‹€λ©΄ κ·Έ μ§μ „μ˜ 집은 νŒŒλž€μƒ‰μ΄λ‚˜ μ΄ˆλ‘μƒ‰μΌ 것이닀. μ΄λ ‡κ²Œ ν˜„μž¬λ₯Ό 기점으둜 κ³Όκ±°λ₯Ό μΆ”μΈ‘ν•˜κ³  이λ₯Ό μ ν™”μ‹μœΌλ‘œ λ‚˜νƒ€λ‚Ό 수 μžˆλ‹€.

μ†ŒμŠ€ μ½”λ“œ

import sys

N = int(sys.stdin.readline())
rgb = [[0, 0, 0]]

for _ in range(N):
  r, g, b = map(int, sys.stdin.readline().split())
  new_r = r + min(rgb[-1][1], rgb[-1][2])
  new_g = g + min(rgb[-1][0], rgb[-1][2])
  new_b = b + min(rgb[-1][0], rgb[-1][1])
  rgb.append([new_r, new_g, new_b])

print(min(rgb[N]))

Written by@μ½”λ”©ν•˜λŠ”νŽ­κ·„
μ§€κΈˆμ€ ν•˜κ³  싢을 λ•Œλ§Œ κ³΅λΆ€ν•©λ‹ˆλ‹€πŸ€—

GitHubInstagramAI Notebook