글 읽기 - 그리디 하게 풀면 안되는거 아닌가요?

tuscanigt 8년 전 0

3 5000

1
1000
1500

로 인풋이 들어왔다고 하면

그리디 하게 풀었을 시 503

근데 실제로는 1000 + 1000 + 1500 + 1500 = 5000 으로 4개면 만들수 있는것같네요

잘못 이해하고 있는건지 궁금합니다

joonas 8년 전 0

A₁ = 1, i ≥ 2인 경우에 A_i는 A_i-1의 배수) 라는 조건때문에 그리디가 가능합니다.

갑자기 dp로 풀어야되나 해서 심장 쫄깃했네요.

tuscanigt 8년 전 1

그런 조건이 ?!

역시 문제는 자세히 읽어야하네 ㄷㄷ

joonas 8년 전 0

노안이 찾아온겁니다.

조심스럽게.

그렇게.

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