D - Diamonds [문제링크]
다이아몬드가 있는 동굴이 여러 개 있습니다. 어떤 두 개의 연속된 동굴에서 같은 색의 다이아몬드를 선택하지 않는다고 할 때, 최대로 얻을 수 있는 다이아몬드의 수를 구하는게 문제입니다.
이 문제는 Dynamic Programming(이하 DP)을 사용하여 풀 수 있습니다.
문제에서는 색깔을 red, blue, purple 로 정의했네요. 여기에서는 red를 0번째, blue를 1번째, purple을 2번째 색깔이라고 놓고 풀겠습니다. :-)
[spoiler="더 보기..."]table[i][j] = i번째 동굴에서 j색깔의 다이아몬드를 선택할 때의 최대 값[/spoiler]
DP에서 테이블을 정의한 다음에는 테이블간의 관계를 정의합니다. 문제에서 테이블의 관계를 나타내어 주는 문장은 아래와 같습니다.
[spoiler="더 보기..."] "he won't choose the same kind of diamonds in any two consecutive caves" [/spoiler]
즉, i번째 동굴에서 j색깔의 다이아몬드를 선택한다면 i - 1번째 동굴에서는 j색깔의 다이아몬드를 선택할 수 없다는 말이 되지요. 이 조건으로 관계식을 만들면 아래와 같습니다.
[spoiler="더 보기..."] table[i][0] = value[i][0] + max(table[i - 1][1], table[i - 1][2]);
table[i][1] = value[i][1] + max(table[i - 1][0], table[i - 1][2]);
table[i][2] = value[i][2] + max(table[i - 1][0], table[i - 1][1]);
[/spoiler]
주어진 점화식을 살펴보면 table[i]에서의 참조값들은 table[i - 1]만 저장하고 있어도 구할 수 있다는 것을 알 수 있습니다. 따라서 배열을 shift해 준다면 1차원 배열만 사용해도 이 문제를 해결할 수 있습니다.
astein
D - Diamonds [문제링크]
다이아몬드가 있는 동굴이 여러 개 있습니다. 어떤 두 개의 연속된 동굴에서 같은 색의 다이아몬드를 선택하지 않는다고 할 때, 최대로 얻을 수 있는 다이아몬드의 수를 구하는게 문제입니다.
이 문제는 Dynamic Programming(이하 DP)을 사용하여 풀 수 있습니다.
문제에서는 색깔을 red, blue, purple 로 정의했네요. 여기에서는 red를 0번째, blue를 1번째, purple을 2번째 색깔이라고 놓고 풀겠습니다. :-)
[spoiler="더 보기..."]table[i][j] = i번째 동굴에서 j색깔의 다이아몬드를 선택할 때의 최대 값[/spoiler]
DP에서 테이블을 정의한 다음에는 테이블간의 관계를 정의합니다. 문제에서 테이블의 관계를 나타내어 주는 문장은 아래와 같습니다.
[spoiler="더 보기..."] "he won't choose the same kind of diamonds in any two consecutive caves" [/spoiler]
즉, i번째 동굴에서 j색깔의 다이아몬드를 선택한다면 i - 1번째 동굴에서는 j색깔의 다이아몬드를 선택할 수 없다는 말이 되지요. 이 조건으로 관계식을 만들면 아래와 같습니다.
[spoiler="더 보기..."] table[i][0] = value[i][0] + max(table[i - 1][1], table[i - 1][2]);
table[i][1] = value[i][1] + max(table[i - 1][0], table[i - 1][2]);
table[i][2] = value[i][2] + max(table[i - 1][0], table[i - 1][1]);
[/spoiler]
주어진 점화식을 살펴보면 table[i]에서의 참조값들은 table[i - 1]만 저장하고 있어도 구할 수 있다는 것을 알 수 있습니다. 따라서 배열을 shift해 준다면 1차원 배열만 사용해도 이 문제를 해결할 수 있습니다.
17년 전