폭은 같고 높이가 다른 그림을 폭은 완전히 겹쳐서 배치 하는데, 폭이 같아서 높이 차이 만큼만 보이게 되거나 높이가 더 작은 것은 안 보일 수도 있다. 이렇게 배치할 때, 보이는 부분의 세로길이(높이 차)가 s이상인 그림만 팔리고, 각 그림마다 높이와 가격이 주어질 때, 적절히 배치하여 판매 가격을 최대로 하는 문제이다. 판매 가격의 최대값을 구해야 한다.
예전에 풀려고 했다가 틀린 문제인데, 그 당시 어떻게 접근했었냐면, LIS를 푸는 방식으로 접근 했었다. 일단 sorting을 해주고, 차이가 s이상 나는 조건을 넣어 각 그림까지의 판매 가격의 최대값을 구해나가는 식이었는데, 그 당시에는 O(N제곱)알고리즘을 썼기 때문에 시간초과가 났다.
그래서 이번에는 (NlogN)방식을 써보려고 했는데 그냥 길이만 구하는 방식이라 판매가격 합의 최대값을 구하는 것에는 적용하기 힘들어 보인다... 음... 더 생각해 봐야겠다.
일단 어떤 분의 블로그를 읽고 이분탐색을 사용하는 부분을 완벽히 이해는 못했지만 실마리를 얻어서 그림을 높이 순으로 정렬 후 선택하고 넘어가는 경우, 선택하지 않고 넘어가는 경우로 나눠서 풀려고 했다. d[n][0]=n번재 그림을 선택하지 않은 경우의 판매가격 최대값
d[n][1]=n번재 그림을 선택한 경우의 판매가격의 최대값.. 이런식으로 놓고 했는데, 문제는... 선택을 한 경우 다음에 선택을 하는 것은 높이 비교가 쉽지만, 선택을 하지 않았다가 선택할 경우 가장 최근에(바로 직전에) 선택했던 것과 높이 비교를 해야해서 parameter로 높이를 보내기로 했는데, 답은 잘 나오는데 계속 WA를 받았다.
그래서 분석해보니... 바로 직전 높이를 보내주기 때문에, 바로 직전 높이에 따라 값이 달라지기 때문에 바로 직전 높이를 memoization배열로 놓지 않으면 적절치 않은 값이 memoization될 수 있다. 즉 잘못된 값을 memoization할 수 있다. 하지만 높이의 범위는 무려 2천만...이미 n만해도 30만인데...
그래서 이제 왜 이분탐색을 해야하는지, 어떻게 풀어야 하는지 찾아보려고 한다.
이 문제가 KOI 2012 기출문제여서 한국 정보 올림피아드 사이트에 가봤는데, 감사하게도 친절한 해설이 있었다.
아... 해설을 보니 lis같은 dp인 것 같다. 단 O(N제곱)알고리즘이 아닌 것이...정렬이 되어있다고 하면 d[i]=i를 마지막으로 선택했을 때의 판매가격 합의 최대값 이라고 하면,
d[i]=max(d[1], d[2]., ..., d[i-1])+c[i]인데, 원래 max(d[1], d[2]., ..., d[i-1]) 바로 이 부분에서 1부터 i-1까지 최대 n-1번을 순환해야 하기 때문에 n제곱이 되는 것인데, 저렇게 최대값을 구하는 부분에서 매번 n번을 순환할 것이 아니라 최대값을 구하면 저장을 해놔서 매번 n번이 아닌 1번만에 최대값을 구하자는 것 같다. 음 이 방법이 일단은 코드로 안짜고 이해만 한 것인데, 왜 lis에서 이런 좋은 방법을 안썼지? 내가 이해를 잘 못 한건가? 이런 좋은 방법을 생각 못한 것도 이상하고...한 번 lis에서 먼저 써봐야겠다...
- 역시나 내가 잘못 생각한 것이었다... lis같은 경우, 자기 자신의 원소보다 작은 값들 중에 최대를 찾는 것이기 때문에.. 즉 자기 원소보다 작은 지를 체크 해줘야 하기 때문에.. n만큼 돌아야 한다. 하지만 이 문제는 다르다. lis처럼 딱 주어진 순서에서 찾는 것이 아닌 주어진 것들을 임의로 재배치할 수 있기 때문에 일단 sorting을 해보면 i번째 원소의 높이보다 s만큼 작은 높이를 가진 k번째 원소를 O(N)만에 구해놓을 수 있고, 즉, d[i]=max(d[1],...d[k])+c[i] 가 되는 것이다. 이 때, lis의 경우 i의 값이 더 작아질 수도 있고 d[1]부터 d[k]중에 d[i]보다 작은 조건을 체크해줘야 했기 때문에 max값을 저장해놔도 사용할 수 가 없었는데, 이 문제의 경우 재배치가 가능하므로 즉, sorting을 하고 k를 구해놓으면 항상 k번째 이하의 원소들은 i번째 원소의 높이 보다 s이상 만큼 작기 때문에 max값을 d[i]를 구해가면서 max[i]=d[i]까지의 max값 <= 이렇게 저장해놓으면 max값을 O(N)만에 구할 수 있고 결국 sorting에 드는 시간 NlogN이 가장 큰 시간이 된다. 결국 O(NlogN)만에 풀 수 있다.
내가 여태 lis도 완벽히 이해 못했다는 것을 알 수 있었고, 이 문제는 알고보면 어려운 문제는 아닌 것 같은데... 아니다 어려운 문제이다... 좋은 문제 같다. 그나저나 이분탐색은 어디에서 쓰는지 모르겠지만 다양한 풀이가 존재할 수 있으므로 일단 저 방식으로 풀어보고 다른 사람의 풀이도 참고해 봐야겠다.
이분 탐색은 지금 선택한 그림과 s이상 차이 나는 것 중 최대 높이의 그림을 찾는데 쓰이는 것 같다. 그리고 위에서 원래 하려 했던 선택하지 않는 경우와 선택하는 경우로 나누는 방식에서 나처럼 하면 문제가 생기지만, 일단 배열도 1차원 배열로 놓고, d[i]=i번째 그림을 마지막으로 선택했을 때의 최대값으로 놓으면 되고 선택하지 않는 경우는 굳이 표시해줄 필요 없이 그냥 선택하지 않고 넘어가면 되는 것이다. 그리고 어떤 그림i를 선택했다면 i의 높이보다 s이상 작은 그림부터 본다(그 그림과 i사이의 그림들은 다 뛰어 넘는다 즉 선택하지 않는다). 그렇기 때문에 바로 직전에 선택한 그림의 높이를 따로 보내줄 필요도 없다. 어차피 거기서부터는 뭘 선택하든 직전 높이와 s이상 차이가 나기 때문이다. 결국 점화식을 보면 lis방식이랑 비슷하긴 한데 일단 재귀로 한 번 풀어봐야겠다. 뭔가 내가 위에서 생각했던 것과 별 차이 없는 것 같아도 엄청 큰 차이가 있다. 조금만 변형한 것 같은데도 훨씬 깔끔하고 문제를 풀 수 있다... 한 번 이 방법으로도 풀어봐야 겠다. 일단 이분탐색을 쓰지않고 풀어보고, 이분탐색을 써서도 풀어봐야겠다.
이분탐색을 쓰지 않고 푸니까 시간초과가 떴다. 이분탐색을 쓰지 않으면 지금 선택한 그림과 s이상 차이나는 것 중 최대 높이의 그림을 찾는데 최대 O(N)의 시간이 걸리므로 O(N제곱)가 된다. 그럼 이제 이분탐색을 써봐야겠다. 아 그리고 이렇게 점화식을 세우고 이분탐색을 쓸 수 있는 것은 그림의 높이 기준으로 sorting을 했기 때문이다. 이 문제에서는 sorting이 매우 중요하다.
이분 탐색을 이용해서 풀었는데 처음에 runtime error가 떴다. 이유는 이분탐색을 이용해서 지금 선택한 그림과 s이상 차이나는 것 중 최대 높이의 그림의 idx를 찾는데, idx를 0으로 초기화 안해준 상태에서 while(l<=r)의 while문에 아예 안 들어갈 경우 idx에 쓰레기 값이 들어가있고 결국 그것이 runtime error를 발생시킨 것 같은데, 해결책으로는 idx를 0으로 초기화해야 한다. while문에 들어가지 않을 경우, idx는 0이되어 결국 dp(idx)는 0을 반환한다.
그래서 결국 AC를 받았다.
출처 : 한국 정보 올림피아드 KOI 기출문제 https://www.digitalculture.or.kr/koi/selectOlymPiadDissentList.do
댓글 없음:
댓글 쓰기