rdd6584   1년 전

탐색 가능한 범위를 절반으로 잘라 그 지점을 이분탐색의 상한으로 잡았습니다.

그리고

i~mid의 범위만큼을 k로 잡고 붙어 있는 다른 k개 만큼의 합을 각각 fsum, esum으로 표현해서 탐색을 반복하는 방식으로 풀었는데요.


자꾸 0프로에서 틀렸습니다가 나오네요. 제가 문제를 잘못 이해한 걸까요? 아니면 구현에서 실수가 있는걸까요? 도와주세요.

chogahui05   1년 전

아!! 이 문제가 어려운 이유는 그 방법이 안 통해서이지요.

5번 치고는 어려운 편이였고요. 본 대회에서 44팀만이 풀었어요. 11% 정도만 완벽하게 맞춘 셈인데요.


예를 들어서 이런 경우를 생각해 봅시다.

8 2 3 1 3 5 6 2


4개씩 묶으면 14, 16 = 16이 나오죠.

3개씩 묶으면 13, 9 = 13이 나오니까. 사실 4개씩 묶었을 때 최대치 >= 3개씩 묶었을 때 최대치니까 저 방법이 통할 것인지도 모릅니다만..


[1] 1 1 8 6 5 1 1을 생각해 보면.

[] 부분부터 봤을 때


4개씩 묶으면 최대치가  11, 13이라 13일지도 모르겠지만.

3개씩 묶으면 이보다 더 큰 19이지요.


고로 저렇게 세워버리면 f(x)가 증가했다가 감소했다가 증가했다가 감소해버리는

이상한 형태가 되어버립니다.

rdd6584   1년 전

와 그렇네요.. 제가 너무 단순하게 생각하고 있었습니다. 답변 정말 감사합니다.

chogahui05   1년 전

이분, 삼분 같은 걸 쓰기 위해서는

그래프 개형이 어느 정도는 나와줘야 하는데. 저 상태로는 써먹지를 못해요. cos, sin이야 주기를 가지고 일정하게 증가했다 감소했다 그러지만.

저건 그러지 않거든요. 증가했다가 감소했다가 하는 주기가 불규칙하거든요.


변하지 않은 성질 같은 것을 기준으로 잡아보세요.

조건을 만족하는 부분 수열의 길이는 짝수라는 게 결정적인 힌트입니다.

rdd6584   1년 전

답변 감사합니다. 말씀하신 것들 고려해서 다시 도전해보겠습니다.

저는 바보처럼 2번째 k번째 집합의 시작점이 바뀌는걸 전혀 고려하지 못했네요..


생각보다 어렵겠네요

댓글을 작성하려면 로그인해야 합니다.