[일반] e번 풀이 급구

[익명(211.197)]

e에 1.5시간 박았는데 결국 tle..

O(n)으로 했는데 아닌가요?

정해부탁드립니다..ㅜ

[익명(211.197)]

아 처음에 minimum 구해서 nlog n으로 햇네요

[익명(211.197)]

뇌정지 온듯 O(n)

[익명(182.231)]

그냥 caes work임 인접한거 2개 없애거나 2칸 떨어진거 2개 없애거나 아예 떨어진거 2개 없애거나

[익명(211.197)]

음 그렇게 했는데.. 머징

[익명(182.231)]

그랬는데 틀린거면 계산을 잘못한거지

[익명(211.197)]

tle라서 로직이 틀린줄;

[노는게제일좋아(aig0016)]

전 쏴서 맞추는 거 전략 종류가 5개길래 5번 O(n) 돌렸어요

[노는게제일좋아(aig0016)]

윗분처럼했는데 인접 없애는 걸 3개로 나눠서 생각함

[익명(211.197)]

생각해보니 굳이 minimum을 구할 필요가 없었네요;

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

O(n)맞아요 답이 될 수 있는 종류가 3개인데 1) 임의의 i,j위치 고르는것. 이것은 a_i중 가장 작은거 2개 골라서 적당히 /2해서 더해주면 됩니다. 2) i와 i+1을 고르는것. 이것은 적당히 연립방정식 세워서 처리해야해요. 3) i와 i+2를 고르는것. 이것은 i,i+1,i+2 각각 몇개 고르느냐에 고려해야하는데 사실 (x[i]+x[i+2]+1)/2입니다. 이 3가지중의 min하면 되요

[익명(211.197)]

감사합니다 선배님

[익명(123.109)]

저는 2개로 되면 arr[i], arr[i+1]을 각각 a번, b번 쏜다고 하면 2a+b >= arr[i], a+2b >= arr[i+1] 이니깐 3(a+b) = arr[i]+arr[i+1] 즉 a+b = 두개합/3 의 올림. 으로 구했어요 이것만 하면 기본예제 안돌아가는데 3개에서 되는경우가 arr[i-1], arr[i], arr[i+1] 의 경우 벡터에 arr[i-1], arr[i+1], (arr[i]+1)/2 넣고 sort 해서 중간값을 답으로 고려하고 완전 떨어진거 2개 되는경우로 입력값 소팅하고 젤 작은 2개 (x+1)/2 합도 고려했어요

[익명(211.197)]

보니까 로직은 맞았는데 쓸데없는 코드가 많아서 tle난거 같네요..

[익명(123.109)]

ㅠㅠ

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(211.197)]

ㅠㅠ..