각 단계마다

마지막 단계에 R이라는 색깔을 이용하여 집을 칠했을 때 최소 비용,

마지막 단계에 G라는 색깔을 이용하여 집을 칠했을 때 최소 비용,

마지막 단계에 B라는 색깔을 이용하여 집을 칠했을 때 최소 비용

은 절대 변하지 않습니다. 즉, 위의 최소비용이라는 답이 아예 정해져있다는 뜻이죠.

그니까 이것을 dp식으로 세우면 되겠네요,

이 문제는 위와 같이 풀 수 없습니다. 접근방식이 아예 잘못되었습니다.

r부터 시작한다면 그 방법은 무수히 많은데 당장 다음단계만 해도 2가지 중 한가지를 선택해야 하죠.

그런데 당연히 최소를 선택하면 안돼요... 그 다음 단계에서 더 작은 값을 선택할 수 없는 경우도 있으니까요

예를 들면 눈앞에 1이 제일 작아서 얘를 선택했는데, 얘를 선택했기 때문에 그 다음에 나오는 최소값 1을 선택할 수 없을 수도 있죠. (인접한건 선택을 못하니까...) 그럼 지금 당장 최선은 아니지만 눈앞에 2라는 숫자가 있어서 그 친구를 선택한 다음에 그 다음에 나오는 최소값 1을 선택한다면 좋은 선택이 되겠죠.

1 1 1

3 2 1

3 9 1

위의 경우가 대충 이런 느낌입니다. 답은 1->2->1이죠.

흠.. 설명하신 부분이 잘 이해가 가지 않습니다.. ㅠㅠ

제가 설계한 대로 푼다해도

R에서 출발할 경우 1->1->3 =5

G에서 출발할 경우 1->1->3=5

B에서 출발할 경우 1->2->1=4

로 저장되어 출력값이 4가 되고 경로도 1->2->1의 형태를 따릅니다. 

조금 더 풀어서 설명해 주실 수 있을까요 ㅠㅠ??

죄송해요, 제가 예제를 잘못 들었네요.

1 10 100

100 5 50

100 20 100

이렇다면 R에서 출발한 경우 1->5->100 :106

G에서 출발한 경우 10->50->20: 80

B에서 출발한 경우 100->5->20: 125

입니다.

하지만 답은 1->50->20:  71이죠.

그럼 이걸 어떻게 푸냐는건데..

i번째 집을 R로 칠하게 되는 경우 1부터 i번째 집까지 칠하는데 드는 최소비용은 유일합니다.

그러니까 이게 막 i+1번째 집을 칠하는 방법이 새로 주어진다고 해서 i번째까지 칠하는 최소비용이 100원이 됐다가 1000원이 됐다가 하지 않잖아요?

그럼 dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + 현재를 Red로 칠하는 비용; 형태로 쓸 수 있겠죠?

즉, dp[i][R]이라 함은 1부터 i번째 집까지 집을 칠해왔는데 맨 마지막인 i번째 집을 Red로 칠하는 방법인 셈이죠.

그런데 그러한 방법은 1부터 i-1번째 집까지 집을 칠해왔는데 맨 마지막인 i-1번째 집을 Blue나 Red로 칠하는 방법중 최소비용인 것을 택한 뒤 현재 i번째 집을 Red로 칠하는 방법이겠죠?

그럼 이걸 dp[i][R],dp[i][B],dp[i][G] 세가지를 i는 N일때까지 다 구해서

셋중에 최소인게 답이겠죠.ㅎ

이제 막 입문하신것 같은데,

개인적으로 http://book.naver.com/bookdb/book_detail.nhn?bid=7... 이 책 추천해드립니다.

종만북보다 초반에 보기 쉬워요. :)

와.. 이렇게 푸는 거군요 

책 추천까지.. 정말 감사합니다 ㅠㅠ 

사실 구종만님 책 사놓고 어려워서 보지도 못하구 있었는데 추천해주신 책 사서 봐야겠어요 ㅠㅠㅠ

감사합니당!!!

죄송합니다만.. ㅋ

위의 예제설명 또 틀렸네요

B에서 출발한경우 100->5->100: 205가 되겠네요.

혹시나 해서 덧붙이자면, mylee님 코드로 했을경우게 그렇게 된다는 거였습니다. 넵넵... ㅎ

네 ㅋㅋ 그 부분은 이해했어요 ㅋㅋㅋ

친절한 설명 다시 한 번 감사드립니다 !