NHN 4번 풀이 어떻게 했냐?

[익명(221.167)]

까먹었다

아메리카노 준다

[마리오(211.206)]

그리디래대충 연승나오는구간 이랑 다 패배했을때중 더 큰점수인 경우로 하는걸로 알음

[익명(221.167)]

연승구간 사이에 1칸 정확히 차이나면 첫 패배를 하고 연승 달리는게 더 나음?

[익명(116.33)]

ㅁㅕㄴㅈㅓㅂㅈㅜㄴㅂㅣ ㄱㅏㅌㅇㅣㅎㅐ

[익명(116.33)]

1ㅊㅏ 면접때 라코볼수도있음

[조성호월챔우승(sonado236)]

그냥 지나가는 사람인데 문제보니까 첨에 연승하면서 시작함 ㅡ> 막히는경우 맨 왼쪽에서 패한다고 생각 ㅡ> 이대로면 O(n^2)지만 막혔을때 넘어가기 위해 필요한 값과 K값과 연승값을 비교해보면 O(1)내에 한번에 계산해서

[조성호월챔우승(sonado236)]

막히더라도 O(1) 내에 넘어가서 결과적으론 O(N)의 그리디식 풀이가 정답이지않을까?

[조성호월챔우승(sonado236)]

현재 연승구간의 보너스점수를 잃는대신 K값을 얻을수있어서 필요포인트를 K*(필요라운드) 식으로 계산하면 되지않을까?

[조성호월챔우승(sonado236)]

1 1 1 에서 3승리 8포인트 다음 관문은 10포인트면 부족한건 2포인트 K값이 5니까 처음 1패는 당연하게 O(1) 내에 계산할 수 있지

[조성호월챔우승(sonado236)]

결국 연승시 얻는 포인트가 많아질수록 K값을 통한 패배가 의미없어지기때문에 연승포인트가 K값을 초과하는순간 막히면 답이 없다고 결론이 나오지