nayuta9010   1년 전

LpAOGZi.jpg

위와 같은 알고리즘으로 해결해 보려고 했습니다.

우선 최소 최대값을 예상해보고 정답을 이진탐색으로 계속 예측해서 풀어보았습니다..만은

틀렸다고 나오네요..

알고리즘상에 문제가 있는건지 아니면 반례가 있는건지 궁금합니다 ㅠ_ㅠ


koosaga   1년 전

  1. 정답을 이진탐색으로 예측하는 것은 맞지만. 정답을 판별하는 그리디 알고리즘이 틀렸습니다.
폭이 2일때 (1,5) / (1,100) / (1,100) 을 넣어보시면 짐작이 가실 겁니다.



koosaga   1년 전

번호는 에디터 문제때문에.. 무시해주세요

nayuta9010   1년 전

정답이 가로라고 가정하고 알고리즘을 푸는것은 가능한데

정답이 세로라고 가정하고 문제를 풀려니 꼬이네요.. 제가 무언가 잘못생각하고 있는걸까요 ?

nayuta9010   1년 전

음.. 정확히 말하면 정답의 범위를 가정하고 이진탐색으로 찾아 나가는데

그 정답이 가로인지 세로인지 모르는 상태에서 가로라고 가정하고 위와 같이 풀었는데 생각해보니 세로일 가능성도 있기에

세로라고 가정하고 푸는 소스를 짜려고 해보니 상당히 난해하더군요.

제가 맞게 생각하는지 아니면 뻘짓을 하고 있는지 답답합니다. ㅠ

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