1182번 - 부분수열의 합
주어지는 N개의 정수 중 **중복된 값이 없다는 조건**이 추가되면 더 정확한 문제가 될 것 같습니다.
'수열'이란 각 항에 순서가 매겨진 데이터인데, 중복이 허락되어 가령 수열이
1 2 1
이고 합이 3이 되는 부분수열을 구해야 할 경우
초항과 둘째항인 (1, 2)와
둘째항과 셋째항인 (2, 1)은 서로 다른 수열로 취급되어야 하기 때문입니다.
현재 조건에서는 permutations이 아닌 combinations으로 정답이 뜨는데 이는 위의 두 부분수열을 같은 아이템으로 취급하는 것 같습니다.
단순히 숫자가 같다고 해서 같은 아이템으로 취급하지는 않는 것 같습니다.
들어주신 예시의 1 2 1에서 첫번째 1과 세번째 1을 다르게 취급하는 것과 같습니다.
그래서 combinations로 했을 때 정답이고, permutations의 경우 똑같이 첫번째 항과 두 번째 항을 포함하더라도 (1, 2)와 (2, 1)을 서로 다른 두 개의 경우로 생각할 것이므로 이 문제의 답을 5로 출력하게 됩니다.
댓글을 작성하려면 로그인해야 합니다.
stophackingme 4년 전 1
주어지는 N개의 정수 중 **중복된 값이 없다는 조건**이 추가되면 더 정확한 문제가 될 것 같습니다.
'수열'이란 각 항에 순서가 매겨진 데이터인데, 중복이 허락되어 가령 수열이
1 2 1
이고 합이 3이 되는 부분수열을 구해야 할 경우
초항과 둘째항인 (1, 2)와
둘째항과 셋째항인 (2, 1)은 서로 다른 수열로 취급되어야 하기 때문입니다.
현재 조건에서는 permutations이 아닌 combinations으로 정답이 뜨는데 이는 위의 두 부분수열을 같은 아이템으로 취급하는 것 같습니다.