[백준] 1149: RGB거리 - 파이썬[python]

풀이

• 동적 계획법을 여러 문제 풀면서 파이썬에서 DP의 가장 중요한 건 계산한 걸 다시 계산하지 않기 위해 전까지의 결과를 저장해놓는 것이다.
• 근데 RGB로 칠할 수 있는 가짓수는 2^(N-1)... 그래서 최솟값을 구하라고 했던 것이다.
• 전의 문제랑 비슷하게 입력으로 받은 다차원 배열을 2째 줄부터 최솟값으로 채워나가면 된다.
• 예를 들어 예제 입력1의 경우를 살펴보자.
  
  • 2째 줄의 49는 1째 줄의 40이나 83 다음에 올 수 있다.
  • 즉, 해당 수(49)는 min(40, 89)+49=89로 채워넣으면 된다.
  • 그러면 둘째줄은 49 60 57에서 89 86 83으로 바뀐다.
  • 다음 줄도 마찬가지다. 예를 들어 99일 때를 보면, 앞 줄에서 89과 86 중 작은 수와 99를 더한 값으로 바꾸면 된다.
  • 그러면 문제에 주어진 i-1, i, i+1가 모두 다른 색으로 칠해진 비용의 최솟값들을 구할 수 있는 것이다.

코드

import sys
input = sys.stdin.readline

N = int(input())
price = [[0] * N for _ in range(N)]

for i in range(N):
    price[i] = (list(map(int, input().split())))

for i in range(1, N):
    price[i][0] = min(price[i-1][1], price[i-1][2]) + price[i][0]
    price[i][1] = min(price[i-1][0], price[i-1][2]) + price[i][1]
    price[i][2] = min(price[i-1][0], price[i-1][1]) + price[i][2]

print(min(price[N-1]))

배열 선언에서 * 연산자

• 다차원 배열을 선언하면서 알게된 사실! GPT 피셜 는 1번만 쓰는 게 좋다고 한다. 왜냐면 는 같은 리스트를 그대로 복사하는 것이기 때문에 하위 리스트가 같은 리스트를 가리키게 된다.
  • 예를 들어,

  arr=[[0]*3]*3

  이렇게 쓰면 arr[0][1], arr[1][1], arr[2][1]는 모두 같은 객체를 가리키게 되어 arr[0][1] 값을 바꾸면 arr[1][1], arr[2][1]도 같이 바뀌게 된다.
  • 그래서 for문을 포함해서 작성했다.

---

음 근데 이건 1차원 배열에서도 마찬가지 아닝가..?
'* 연산자'가 단순 얕은 복사라면 1차원 배열도 같은 리스트를 가리켜서 arr[0]을 바꾸면 arr[1]도 바뀌는 식으로,,, 라고 생각했는데,..!! 더 찾아보니까

• 1차원 배열에서

  arr=[0]*3

이런 식으로 선언하면 0은 숫자 즉, 불변 객체이기 때문에 문제가 없고,

• 2차원 배열에서

  arr=[[0]*3]*3

이렇게 쓰면 각 요소가 모두 같은 리스트(가변 객체)를 참조하기 때문에 문제가 되는 것이다!!!!

---

• 어쨌든, 우리 코드에서 굳이 2차원 배열로 선언 안하고 아래와 같이 해도 된다. 첫 번째 for문에 모두 접근 가능한 인덱스만 사용하고 있기 때문이다!

price = [0] * N

• 이렇게 하고 첫 번째 for문에서

price[i] = (list(map(int, input().split())))

이렇게 쓰면 각 값들이 리스트로 바뀌게 되어 2차원 배열이 되는 것이다.

결과