chogdak   1년 전

검색해보니 동적 프로그래밍으로 풀라는데 동적 프로그래밍의 조건이 부문제들이 독립적이여야한다는거 아닌가요?

근데 이 문제는 부문제들이 독립적이지가 않은거같아요.

예를 들어

R G B

1 1000 2000 999

2 1001 1000 999

3 1 1001 9999

여기서 3까지는 최소가 BGR인데

네 번째 검사할때

R G B

1 1000 2000 999

2 1001 1000 999

3 1 1001 9999

4 1 9999 9999

여기서는 4까지의 최소가 RBGR로 바뀌는데 (겹치는 걸로 인해서 첫항까지 다 바꿔야하죠...)

이걸 어떻게 동적 프로그래밍으로 풀 수 있는지 궁금합니다.

항이 추가될 때마다 그 전 항의 정보를 바꿨는데 바꾼게 또 그 전의 항이랑 겹쳐서 그 전 항도 바꾸고 그 전 것도바꾸고

이런식으로 쭉 이어지는 경우가 생긴다면 그게 동적으로 풀 수 없는거 아닌지...


kesakiyo   1년 전

세번째일때의 최솟값이 아니라

세번째에서 몇번째 집에까지 있는지를 고려를 한다면 조금 달라지지 않을까요?

csehydrogen   1년 전

점화식을 정확히 정의하고 시작해보세요
예를 들어, d[i][색깔] = i번째 집에 (색깔)을 칠했을때, 1~i번째 집까지 칠하는데 최소 비용

댓글을 작성하려면 로그인해야 합니다.