operaghost   2년 전

시간 복잡도를 줄이기 위하여 

***** 체크한 부분을 추가하였습니다.

처음에는 if(x >= 2 * y)로 시도를 해보니 되지 않아서

엉겹결에 3배로 바꾸었더니 통과를 하였습니다.

몇 일동안 첨에 시도한 경우는 왜 되지 않는지 반례를 생각해보았는데

도저히 찾아지지가 않네요.

고수님들의 도움이 필요합니다. ^^

plzrun   2년 전

반례:

36 17
답은 10입니다.
그런데 *2하는 경우 답이 12가 나옵니다.

(한변이 9짜리인 정사각형이 4개, 8짜리가 4개, 4짜리가 2개 => 10개)

*3으로 처리하면 처음 자를 때 

이거말고도 인풋데이터 넣고 비교해보니까 들어가는 인풋 100만개 중 반례데이터는 9495개가 있네요.

몇 개 더 나열해 볼게요.

N M (*3인 경우(정답), *2인 경우(오답))
52 25 (11, 12)
53 17 (11, 13)
60 29 (12, 17)
10000 49 (216, 217)

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