안쓸라 했는데 의심하길래 씀
일단 구간값 들을 계속 더해서 최대가 되게 해야되니까
구간의 개수가 제일 많아야댐.
수열이 짝수개면 2개짜리 구간으로 채우고
홀수개면 3개짜리 하나 나머진 두개 짜리.
그리고 3개짜리 구간에서 사이에 있는 값은 그냥 버려진다고 보면댐
그럼 구간값들의 합 은
(A1-B1)+(A2-B2)+...(Am-Bm) 이 댐.
A는 구간의 최대값
B는 구간의 최소값
수열에 있는 값을 저 식의 각 자리에 대입한다고 생각하샘
그럼 저식은
(A1+A2+A3+..+Am) - (B1+B2+...Bm) 이댐
이걸 최대로 만들어야 되니까
최대값들의 합을 제일 크게 하고
최소값들의 합을 제일 작게 하면댐
그럼 정렬해서 반으로 쪼개서 큰부분의 합 - 작은 부분의 합 을 하면댐
배열의 원소를 재배치 하는게 아니던데요?
복사본 만들면 되지
아니 이 방법은 원소의 순서를 바꿔서 최대로 만든거잔아. 문제는 원소의 순서를 바꾸지 않고 최대로 만드는거고
ㅇㅇ..문제는 문제자체를 재배열할 수 없는게 문제 ㅠㅠ 구간이 3개면 재배열 상태로 3개를 쪼개는게 아니고 사용자가 입력한 상태 그대로에서 쪼개야함.. 입력은 랜덤임. 그래서 의심됐던거임 sorted된거면 상관없는데 그게 아니니까 ㅠㅠ
게시글 늦게봐서 미안함ㅠㅠ 더블릿 정회원이 아니라 다른사이트에서 같은문제 찾아 서미트 해보려고 했는데 없더라구 그래서 정답의 유무는 확인할 수 없뜸
근데 생각해보면 꼭 sorted가 아니어도 상관없다고 생각이 됨.. xxx/57/xxx/xx 이렇게 원소가 9 개인데 피치못하게 5가 들어가게 자를 경우가 -> 차이가 최대가 되도록 구간을 제대로 나눈것인가? 생각해보니 정답을 구하는 수식에 5가 들어가면 20이란 값이 나오지 않을 것같음
근데 다 그냥 안될것같다~ 라는 느낌일 뿐 제대로 된건지 몰라서 예외경우를 찾아보려했지만 헐 찾았다 9개면 123456789가 들어가는게 아니고 원래 문제 자체가 123123123 이렇게도 들어갈 수 있네
실제로 내가 쓴 게시글의 예제가 2 5 7 1 3 4 8 6 9 3 이렇게 들어가있네 ㅠㅠ 10개원소가. 10대신 3이 2번쓰임. 한 숫자가 꼭 한 개 쓰이란 보장이 없었네 헐... 그냥 다이나믹이 답인듯;;
또한 솔림님 ㅠㅠ 구간의 개수또한 입력으로 입력하는 방식이라 .. 그리 간단하진 않네요..ㅠㅠ 아 생각해보니 이렇게는 안되겠구낭...흡..