x축 위에 n개의 사탕 바구니가 놓여있고, 각각의 사탕 바구니 안에는 m개의 사탕이 들어있다. 그리고 주인공은 x축 좌표 0에 위치하고 있다. 주인공이 사탕을 먹는데 걸리는 시간은 0이라하고, 1만큼 움직이는데 걸리는 시간이 1이다. 근데 시간 1마다 각각의 사탕 바구니 안의 사탕이 1개씩 줄어든다. 이 때 주인공이 먹을 수 있는 사탕의 최대 개수를 구해야 한다.
이 문제는 BOJ 2315 가로등 끄기 문제와 유사해 보인다. 기억이 잘 안나서 내가 써놓은 글을 봤더니 이해가 된다. 역시 이렇게 기록해놓길 잘했다.
그런데 완전이 똑같지는 않다. 사탕 바구니의 위치로는 음수 좌표도 있고 사탕 바구니를 방문하는 도중 사탕의 개수가 0이 되버리면 더 이상 방문할 필요도 없다. 그리고 주인공의 출발위치는 0으로 정해져있다.
일단 식을 세워보자. 주인공의 좌표0을 넣어서 sorting을 하고,
d[s][e][where] = 사탕 바구니s부터 e까지 방문한 상태이고 현재 위치는 where(s또는 e)이고, (앞으로 계속 방문해서) 최종적으로 먹을 수 있는 사탕의 최대 개수
좌표 0의 인덱스부터 시작한다. d[idx0][idx0][0], 그리고 parameter로 남은 사탕의 개수m을 보내준다.(재귀로 구현)
if(where==0)
d[s][e]=max(d[s-1][e]+(m-(pos[s]-pos[s-1])), d[s][e+1]+(m-(pos[e+1]-pos[s])));
if(where==1)
d[s][e]=max(d[s-1][e]+(m-(pos[e]-pos[s-1])), d[s][e+1]+(m-(pos[e+1]-pos[e])));
대충 이런식이 되지 않을까 생각한다. 한 번 직접 짜봐야겠다.
좌표 0이 출발 지점이므로 좌표 0을 넣어야 하는데, 만약 좌표 0인 사탕 바구니가 존재한다면, 넣지 않고, 답을 구할 때 시작점의 사탕 개수 m을 더해줘야한다. 그래서 nCnt라는 변수를 이용해서 사탕 바구니가 좌표 0 에 존재한다면 nCnt=n이고, 존재하지 않아서 좌표 0을 추가해야 한다면 cCnt=n+1로 해준다. 그리고 인덱스 범위는 0~nCnt-1이 된다. 인덱스 범위를벗어나지 않도록 주의해야 한다.
그리고 m값이 음수가 될 수도 있는데, 이 경우는 0으로 처리해야 하므로 조건을 따로 넣어주든지 -m값을 return해서 다시 손실된 값을 더해주는 식으로 처리해야 할 것이다.
음 계속 틀린다. 근데 뭐 실수가 아니라 정말 그냥 내 방식 자체가 틀렸다.
가로등 끄기 같은 경우, 어떤 순서로 가로등을 끄면서 왔든 간에 d[i][j][where] 즉, i에서 j까지 끄고 where의 위치에 있으면 그 다음부터는 독립적인 부분 문제이다. 즉, 직전 과정에 영향을 안받는다. memoization이 효과가 있다. 하지만... 사수아탕 문제를 내가 이렇게 짰는데, 여기에는 parameter로 m을 넘겨주는데, m은 직전에 어떤 순서로 어떤 사탕 박스를 거쳐왔냐에 따라 m값이 바뀐다. 그렇기 때문에 같은 d[i][j][where]라도 m값이 다르기 때문에 직전 과정에 영향을 받는 것이고, 값이 다르게 되어 memoization이 의미가 없다...
그렇다면 가장 간단한 해결책은 m을 d[i][j][where][m] 이렇게 추가하는 것인데, 이러면 메모리초과이다. 사실 난 BOI(Baltic Olympiad in Informatics, 이 문제의 출처) 사이트에서 test case를 다운 받아서 내 눈으로 직접 틀린 케이스를 보기 전까지는 내가 틀릴리 없다고 생각했었다. 하지만 정말 예전에 being(류원하)님이 발표에서 하신 말씀처럼.. 사실 내가 멍청한 것이었다. 틀린 케이스를 보고나서, 그제서야 왜 틀렸는지 고민하게 됐고, 이렇게 이유는 알아냈다... 하지만 만약 test case가 없었다면.. 이렇게 생각하기도 한참 걸렸을 것이다. 반성하자...
그래서 결국 어떻게 할 것이냐... 좀 더 고민해봐야 겠다.
음 일단, 구조는 비슷하게 하면서... m을 parameter에 넣어두는 대신 d[s][e][where]=사탕 바구니s부터 e까지 방문한 상태이고 현재 위치는 where(s또는 e)이고, (앞으로 계속 방문해서) 다 방문하거나 m이 0이 됐을 때 총 이동한 횟수 ....
이렇게 해서 이동한 횟수가 가장 큰 경우를 구하고, 구해놓은 것(memoization)을 이용해서 그 경우에 따라 한 번더 재귀를 돌려서 최대값을 찾는다. 일단 이동한 거리는 어떻게 이동 하든 m이하가 될 것이다. 그런데 같은 거리를 이동할 때 이동 횟수가 클수록 즉, 한 번에 조금씩 움직여서 최대한 많은 지점을 방문해야 얻을 수 있는 사탕의 개수가 최대가 될 것이다. 음.. 근데 m이 12이고, -2, -1, 10, 11, 12, 13이 있을 때, 이동 횟수는 같은데, 크기가 달라지는 경우가 나온다. 만약 m이 13이면...이동 횟수가 더 적은쪽이 사탕의 개수가 더 커진다...
아... 다른 방법을 생각해 봐야겠다.
결국 BOI(Baltic Olympiad in Informatics) 사이트에서 풀이를 봤다.
이 문제에서는 각 사탕 바구니까지 이동하면서 줄어드는 사탕의 개수를 dp로 구한다.
이 문제의 접근 방식을 살펴보면, 사탕 바구니에 모두 m개씩 담겨있으므로 구하고자 하는 사탕의 최대 개수는 k개의 사탕 바구니를 방문한다면, m*k-(t1+t2+...tk) (여기서 ti는 i번 바구니를 방문하는 데까지 걸린 시간) 이다. 여기서 바로 k를 정해놓고, 그에 따른 t1+t2+...+tk를 구하는데 dp를 이용한다. k는 최대n이므로 시간 복잡도는 O(n세제곱), 공간복잡도는 O(n제곱)이 될 것이다.
사탕의 최대 개수를 바로 구하는 것이 아니라, 각 사탕 바구니까지의 줄어드는 사탕 개수의 합의 최소를 구한다... 그리고 그 것을 구할 때는 몇 개의 바구니를 방문할 건지 정해놓고 구한다. k를 정하지 않고 그냥 각 사탕 바구니까지의 줄어드는 사탕 개수의 합의 최소값을 구하는 것은 그냥 바로 사탕의 최대값을 구하려고 하는 것과 비슷하기 때문에 힘들다. 내가 하는 방식으로 하면 앞에 어떻게 했냐에 따라 부분 문제가 독립적이지 못하고 영향을 받는다.
하지만 이렇게 k를 정해놓고 할 경우,
k개의 바구니를 방문할 때, d[s][e]=사탕바구니 s부터 e까지 방문한 상태이고, 앞으로 계속 방문해서 최종적으로 각 바구니에서 줄어든 사탕의 개수의 합의 최소값
d[s][e][where]로 해보겠다.(풀이에서는 d[s][e]로 하는 대신 L, R로 나눠서 했는데 나누지 않고 하나로만 하려면 where를 쓰면 될 것이다.)
if(where==0) { //핵심적인 부분만 정리...
d[s][e]=min(dp(s-1, e, k-1)+k*(pos[s]-pos[s-1]), dp(s, e+1, k-1)+k*(pos[e+1]-pos[s]))
}
else {
,,,
}
보면 k-1을 parameter로 보내주면서 k를 하나씩 줄여나가고, (이동한 시간)에 k를 곱해주는 것을 볼 수 있는데, 현재 선택되지 않은 k개의 사탕 바구니의 사탕이 그 (이동한 시간)만큼 줄어들었다는 것을 의미한다. 그리고 지금 사탕 바구니를 하나 선택해서 이제 더 이상 안 볼 것이므로 k-1로 k를 하나 줄여주는 것이다... 이 것을 보면서 한 번 더 충격을 받았다.
원래는 가로등 끄기처럼 접근했다가 틀렸다는 것을 알고 생각해보니 부분문제가 앞에 어떻게 했냐에 따라 영향 받는다는 것을 알고, 가로등 끄기처럼 접근하는 것이 아니구나라고 생각했다가 풀이를 보니 살짝 발상의 전환을 하고(줄어드는 사탕의 개수를 구한다!), 1~ n까지의 k를 놓고 n번 dp를 하는데, 그 dp가 가로등 끄기와 매우 유사한 것을 깨달았다...
아 진짜 난 풀이 안보고는, 새로운 문제를 혼자 생각하지를 못한다. 비슷한 문제여도 똑같은 문제가 아니면 풀지를 못한다... 열심히 해야되는데, 오늘도 이 문제 하나로 고민하다가 딴 짓도 하고 시간 낭비도 많이 했다.
일단, 하나 집고 넘어가야할 것은 이렇게 하면 부분 문제가 앞에 어떻게 했냐에 따라 영향을 받지 않을까? 인데, 그렇다. 아까 영향을 받는 경우는 앞에 어떻게 움직이냐에 따라 같은 부분 문제여도 m값이 다를 수 있게되고 m값이 바뀌면 더해지는 값들도 바뀐다. 하지만 이렇게 하면 d[s][e] 상태에서 s와 e사이의 바구니는 모두 방문했을 것이므로 k값은 같을 수 밖에 없다. 어떻게 방문을 했든 간에 방문한 바구니의 개수는 d[s][e]라면 같을 수 밖에 없고, 또한 k를 정해놓고 함으로써 가로등 끄기 문제처럼 앞으로 몇 개의 사탕바구니가 남았는지 알 수 있기 때문에 지금 어떻게 이동하는지에 따라 전체 바구니에서 몇 개의 사탕이 줄어들고 있는지를 알 수 있다. 즉 가로등 끄기 문제처럼 풀 수 있다.
또한 만약 k개를 정해놓지 않고 하면 문제가 되는 것이, 앞에서 어떻게 움직이냐에 따라 방문할 수 있는 바구니 개수도 달라지게 되어, 즉 부분 문제에 영향을 주게 될 것이다.
이 문제는 가로등 끄기나 김치 배달 문제와 비슷하지만 그 두 문제처럼 모든 가로등을 꺼야하거나, 모든 김치를 배달해야 하는 것이 아니고, 바구니를 방문하는 순서에 따라 방문할 수 있는 바구니의 개수도 달라지기 때문에 그 두 문제와 비슷하게 풀려면 k를 정해놓고 모든 k에 대해 해봐야하는 것이다.
k를 정해놓고 m*k - dp중 최대값을 찾으면 된다.
한 번 풀어봐야겠다.
코드를 짜보는데, 계속 틀린 값이 나와서 고민하다보니... dp재귀 함수 안에서 최소값을 구하기 때문에, 그리고 s>0이 아닌 경우에는 바로 ret값이랑 비교하기 때문에 ret값을 매우 큰 값으로 초기화 해줘야하는데, 초기화해주지 않아서 그런 것이었다...
그리고 위에서도 조금 써놓긴 했는데, 주의할 점으로 좌표0이 입력에 포함된 경우와 포함되지 않은 경우를 잘 생각해야 한다. 나는 포함된 경우는 start=m으로 놓고, start를 답출력할 때 더해줬다. 포함되지않으면 0이 더해지도록 했다. 그리고 k도 포함된 경우, 포함되지 않은 경우에 따라 어디까지 봐야하는지 달라지는데, nCnt란 변수를 둬서 nCnt-1까지만 보도록 했다. AC를 받았다. 정말 험난한 문제였지만 좋은 문제였다.
출처 : Baltic Olympiad in Informatics 2009
댓글 없음:
댓글 쓰기