[일반] 동전문제 수학으로 푸는법 없나?

[익명(121.142)]

https://www.acmicpc.net/problem/2293

다른 사람들 풀이 보니까 죄다 이중 포문으로 i~K까지 구하네

나눗셈 넣어서 포문 하나 제거할 수 있는 방법 없나?

[pichulia(49.172)]

Knapsack 은 쉬운 풀이가 없는걸로 유명한 대표적인 문제여서... 여기서 포문 하나 줄이면 100만달러의 상금과 수학계의 거상이 될 수 있습니다

[익명(121.142)]

그렇구만 심오하네

[익명(14.34)]

와 그정도인가 개쩌네

[익명(77.103)]

O(nk)를 O(n)으로 줄이면 냅색을 다항시간에 푸는게 되는데 냅색의 결정문제는 NP-complete니까..

[붕붕이(182.216)]

포문 하나는 줄일수 있긴함 ㅋㅋㅋ 동전 배열에 넣고 다 비교해서 떨어지면 다음 배열로 가면 됨 시간은 비슷하겠지만 포문 하나는 줄어듬 - dc App

[익명(112.152)]

고민해봤다가 포기했는데 못푸는게 정상이었네 ㄷㄷ

[Gravekper(gravekper)]

그거 해내면 뉴턴이나 가우스 옆자리에 앉을 수 있음