배열 A 의 성분 중 m( 1<= m <= k <= n)개의 성분을 합할때, 0이 되는 경우의 수는?

  • Soboru
    Soboru

    인풋은

    정수 n(배열 A 크기) , k
    배열 A

    이렇게 3가지 입니다..

    (m 이 1부터 k 까지의 모든 경우를 더하는겁니다.)

    이 문제.. 동적프로그래밍으로 구현 가능한가요?

    전 재귀함수로 brute force 방법밖에 안 떠오르네요..

    답변 부탁드립니다.


    10년 전
5개의 댓글이 있습니다.
  • 샥후
    샥후

    배열 A의 숫자들이 작다면 DP로 구현가능합니다.
    제한이 없다면 일반적으론 brute force입니다.


    10년 전 link
  • 일루
    일루

    n이 40~50 정도라면 meet-in-the-middle 도 있습니다.


    10년 전 link
  • Soboru
    Soboru

    샥후, 일루님 답변 감사드립니다. 샥후님 dp 로 어떻게 구현가능한지 조그만 힌트좀 주실수 있나요?


    10년 전 link
  • Being
    Being

    http://en.m.wikipedia.org/wiki/Subset_sum_problem


    10년 전 link
  • Soboru
    Soboru

    Being 님 감사합니다! 덕분에 도움 많이 됐습니다.


    10년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.