[질문] 겨울숲 제가 뇌절한건지 궁금합니다 (스포있음)

[chromat..(hjroh0315)]

A에서 뇌절을 많이 했다고 느껴졌는데, 일단 O(TNlogN)으로 했습니다. T는 최대 시간 (=1440), N은 문제에서 주어지는 N입니다. 현재상태에서 가장 큰 2개 (또는 1개뿐이라면 1개)를 빼는게 최적이라고 생각했고, 아무리 생각해도 끝까지 돌렸다가는 TLE 날거 같아서 최대 1440번만 시뮬레이션 (한번 할때마다 새로 정렬)하고 안되면 -1 찍는 풀이를 썼습니다.

혹시나 더 쉬운 풀이가 있나요?

[ㅇㅇㅇ(110.10)]

가장 큰 수랑 ceil(합/2)중에 큰게 답이에요

[chromate00(hjroh0315)]

와 개간단하네요 감사합니다

[익명(210.0)]

A번이니까 말씀하신 풀이가 문제에서 의도한 정해일듯 하네요

[chromate00(hjroh0315)]

감사합니다

[대학원오지마세요(publfl)]

이런식으로 N개의 묶음중 임의의 2개 골라서 1개씩 빼기 문제가 꽤 자주보여서 알아두면 좋습니다. 최대값 > 나머지값들의 합이면 최대값 만큼의 연산이 필요하고, 그 이외는 나머지 값들의 합만큼 연산이 필요합니다.