라인 인턴 코테 3번 어케푸냐

[익명(223.62)]

무슨 알고리즘이냐 이거

존나어렵넹

완탐돌리면 백만C만이라 무조건 터지고

어떻게 접근해야할지몰라서 3번 못풀고 2솔했는데

[l구름l(delta4ce)]

[익명(59.18)]

걍 수학 아님?

[익명(223.62)]

어케 푸냐공

[l구름l(delta4ce)]

[un(118.223)]

개쉬운데?

[익명(223.62)]

어케 풉니까?

[익명(39.114)]

그리디면 삑날것같은데 흠

[익명(1.241)]

ㅁㅊ 난 이분탐색 썼는데 ㅈㅈ

[익명(223.62)]

아 씨발 그러네 아 연료 1씩주면서 가장 늦게 도착하는애한테만 연료주는방법을 왜생각못했지

[익명(125.141)]

아 씨발 제출하고 나니 이게 더 맞는 것 같네 ㅋㅋ

[익명(211.38)]

O(NM)이면 100억인데?

[익명(39.114)]

범위 모르겠는데 억 넘으면 안되징

[익명(1.241)]

ㄴㄴ 이거 우선순위 큐로 푼거아님? 그럼 MlogN이지

[nu(220.117)]

나도 그렇게 풀었는데 가장 늦게 도착하는 애 구하는걸 heap 써서 logn으로 만듬

[익명(1.241)]

난 이분탐색썼는데 이게 더 효율적이네

[un(118.223)]

MlogN

[익명(39.114)]

그럼됨

[nu(220.117)]

un은 우선순위큐 안쓰고 그냥 O(nm)으로 풀어서 댓글 삭제한듯 ㅋㅋㅋㅋ

[un(118.223)]

ㅎㅎ gg 힙을 당연히 써야지 왜 안 썼냐 이 븅신아

[익명(125.141)]

연료 1씩 다 주고 도착시간 계산 -> 그 도착시간을 sum낸 다음 sum값 대비 각 도착시간 해서 대충 double로 각각 연료 얼마 받아야 하는지 나오는거 반올림 -> 마지막에 연료 0 받은 놈들 1씩 주고 끝

[익명(124.56)]

풀이가 완탐밖에 생각안나서 걍 완탐해버림 - dc App

[익명(223.62)]

그럼터짐

[익명(124.56)]

아는데 못푸는것보단 낫다고 생각해서 - dc App

[익명(125.141)]

그럼 100% 터져서 연료는 따로 구함

[익명(125.141)]

테케 1로 보면 750 / 20, 675 / 30이니까 시간 하면 대충 38 / 23 뭐 이딴 식으로 나오고 그거 비례식으로 한 다음 거기 실 fuel값 곱하면 4.93928745, 3.0123 이딴 식으로 나옴

[익명(39.114)]

난 시간 이분서치-> 안에서 각각 시간때 distance도착시까지 필요한 연료량 이분서치

[익명(1.241)]

오 나도 이렇게 품ㅋㅋ

[익명(1.241)]

이러면 log2T(Nlog2N) 인가

[익명(59.5)]

아 이렇게 풀면되네 ㅅㅂ ㅠ 생각안나서 브루트포스로 풀다가 테케 3개만 맞고 끝나버렷네

[dd(116.127)]

이분탐색 하면 충분히 풀림