❌ 백준 1149 RGB거리
https://www.acmicpc.net/problem/1149
오답.
처음에 너무 단순하게 생각했다.
최솟값들만 뽑으면 될거라 생각했다.
그렇게 코드를 짜서 제출했는데 틀렸다.
코드를 잘못 짜서 그런가보다 싶어서 고쳤다.(그 와중에 반례가 있었다)
근데 또 틀려서 질문게시판에 반례를 찾아보니 문제를 아예 잘못 이해하고있었다.
당장에 최솟값만 고른다고 합이 최소가 되지는 않는다는 것을 깨달았다.
ex)
1 9 2
1 9 9
9 1 9
코드를 싹 지우고, 포기할까하다가 찝찝해서 그냥 힌트를 보기로 했다.
동적 계획법으로 푸는 문제였다.
그러고보니 비슷한 문제를 책에서 본 적이 있었다.
풀이를 조금 참고해서 코드를 짜서 제출했는데 이번엔 Recursion Error가 떴다.
그래서 그냥 제한 10*6까지 늘리고 제출했더니 정답이었다.
로직
입력받은 값들을 3*N의 2차원 배열에 넣는다.
index로 값을 특정하기 위함이다.
비용의 합의 최솟값을 찾는 함수 p(y,x)를 만들건데, 이 함수는 (y,x)에서 가장 아랫집까지의 비용의 최솟값을 구한다.
즉 arr(y,x)의 값에 p( y - 1, 선택가능한 두개의 값 중 작은것 )을 더해주면 p( y, x ) 의 값을 구할 수 있다.
식으로 나타내면 아래와 같다.
p ( y, x ) = arr + p( y - 1, ( x + 1 ) % 3 )
6번 행
: 입력값들을 담을 배열
7번 행
: p(y,x)의 결과 값을 저장하기 위한 배열
10번 행
: arr에 값을 담는 코드
15번 행
:
만약 제일 아래쪽까지 내려왔으면, arr[y][x]값을 반환
18번 행
:
p(y,x)값이 이미 계산되었으면 그 값을 반환
21번 행
:
p(y,x)값이 캐시에 없을 경우 계산해서 23번 행에서 캐시로 추가
27번 행
:
첫번째 집의 rgb중 가장 비용이 적게 드는것부터 시작한 값을 출력.
import sys
sys.setrecursionlimit(10**6)
test_case = int(sys.stdin.readline())
arr = []
ts = [[-1 for x in range(3)] for y in range(test_case)]
for i in range(test_case) :
arr.append(list(map(int,sys.stdin.readline().rstrip().split())))
def p(y,x) :
if y == test_case-1 :
return arr[y][x]
if ts[y][x] != -1 :
return ts[y][x]
val = min((arr[y][x] + p(y+1,(x+1)%3)),(arr[y][x] + p(y+1,(x+2)%3)))
ts[y][x] = val
return val
print(min(p(0,0),p(0,1),p(0,2)))
