-
2156알고리즘/acmicpc 2015. 2. 28. 18:23
바로 전 문제 dp를 쉽게 풀어서 이 문제 만만히 봤는데 4번맞에 맞았다;;
너무 내가 성급히 접근한것 같다. 경우의 수를 좀 철저히 따져봐야 했는데.
문제의 핵심은 연속 3잔은 마실 수 없다는 것이다.
그러면 경우의 수로 나눌 수 있는데
1 2 3 4 5 6 이렇게 포도주가 있으면
12 3 45 6 하나를 공백으로 두고 마시는 경우와
12 3 4 56 두개를 공백으로 두는 경우 그리고
1 2 3 4 5 6 하나씩 공백으로 두는 경우로 나눌 수 있다.
이 문제를 풀기위한 자료구조로 이차원 배열을 생각해냈다
d[][2] -> d[][0]는 현 위치에서 연속이 끝나는, d[][1]는 현 위치에서 연속이 시작하는
위의 모든 경우와 자료구조를 정의했으니 다음과 같은 점화식을 낼 수 있다.
d[here][0] -> w[here]+d[here-1][1]
현위치에서 연속이 끝날때는 바로 전 위치에서 연속이 시작할 때의 값과 더하면 된다.
d[here][1] -> w[here] + max(d[here-2][1], d[here-3][0], d[here-2][0])
현 위치에서 연속이 시작하려면 세 가지 값과 비교해야하는데 바로 전전 위치에서 시작하는 경우와 끝나는 경우 바로 전전전 위치에서 끝나는 경우와 비교한다.
그러면 모든 경우를 포함하게된다.
dp문제는 내가 푸는 알고리즘이 모든 경우를 포함하는지와 중복되지 않는지를 확인하는것이 관건이다. 오늘은 모든 경우를 포함하지 못해서 자꾸 틀렸다;