[CH07]FENCE

[wbluke]

https://algospot.com/judge/problem/read/FENCE

APSS_p195

[wbluke]

[My Point]

• 문제 읽다가 음 해볼까 하다가 분할 정복 알고리즘이 잘 적용이 안되어서 그냥 답을 봤다. 생각보다 복잡했다. 무식하게 풀기에는 Test case의 크기가 너무 컸다.

[Idea Point]

• n개의 판자를 절반으로 나눠 두개의 부분문제를 만들고, 찾고자하는 최대 직사각형이 왼쪽, 오른쪽, 혹은 경계선을 포함해서 걸쳐있는 경우 세가지로 나눈다. 당연하게도 왼쪽이나 오른쪽은 재귀호출을 구현하면 된다.
• 걸친 경우 : 먼저 경계선에 있는 두 판자를 포함하는 직사각형을 설정한다. 그리고 왼쪽 끝, 혹은 오른쪽 끝에 있는 판자의 높이를 비교해 더 높은쪽으로 확장해가며 비교한다.
• 정당성 증명 : 귀류법으로 증명하면 되는데, 각 단계마다 더 높은 판자를 선택해서 확장하는 것이 항상 옳다.

[wbluke]

[My Point]

• vector outofbound 에러가 자꾸 떠서 한시간동안 헤맸다. 2번 commit에서 해결! 그러나 답이 아직 나오지 않았다. 일부 케이스에서 답이 더 나오는 상황. 경우를 더 세분화해봐야겠다. (아이디어는 같으나 책과는 다르게 구현이 되었다. 책이 더 간단한걸... 하지만 고치기엔 늦었다.)

[New Things]

• 벡터의 복사 : vector vec; vector dest; dest.resize( vec.size() ); copy( vec.begin(), vec.end(), dest.begin());

• v.begin()과 v.end()는 iterator다. 범위를 지정할 때도 기존 벡터를 반을 나눈다고 했을 때, fence.begin(), fence.begin() + mid fence.begin() + mid, fence.end() 이런 식으로 나누어야 둘로 나누어진다. 그림을 그려서 생각해보면 헷갈리지 않을 것.

[wbluke]

[My Point]

• 수 번의 시도 끝에 겨우 성공. 문제는 내 풀이법의 복잡도가 책의 풀이보다 복잡했던 것. 나는 울타리의 높이를 저장하는 fence vector를 직접 두개의 벡터로 다시 쪼갠 다음 재귀 호출을 했는데, 책에서는 그냥 구간을 나타내는 left, right 정수 두개만 인자로 받아서 함수를 구현하였다. 어차피 주어진 벡터의 값들은 변하지 않아서, 범위를 지정하는 참조값만 조절해주면 되는 거였는데, 아쉬움이 남는다.

[정 답!]