목표정수 M과 크기 N 이 있습니다.
예를 들어 M이 7, N이 4라고 하면
N의 크기만큼 숫자가 입력됩니다.
5 3 4 7 이 있겠네요.
이 5, 3, 4, 7을 원하는 만큼 더해서 목표정수 M을 만들 수 있나 없나를 true, false 로 나타내려고 하는데
예를들어 7의 경우엔
그냥 7도 되고 4+3 도 되겠네요
문제 자체는 쉬운데,,알고리즘 접근법을 모르겠습니다.
M(0<=M<=1,000)
N(2<=N<=100) 이 조건인데,
브루트포스로 해야하나요...? 시간도 오래걸리고 구현도 복잡할텐데
어떤 알고리즘 접근법을 사용해서 어떻게 푸나요...?
고민해봐도 모르겠습니다...>!!
ex)
input :
10 4
1 2 3 4
output :
true
냅색 dp
오우마이갓.. dp 엄청못하는데
아 문제 다시보니 냅색이랑 비슷한 구석이 많네요 감사합니다
extended euclidean 되려나?
M이 작아서 DP가능
그냥 냅색의 정의 그 자체인데
정렬 후 투포인터도 될거같은데