cpp

[1182] 부분수열의 합

알고리즘 분류 비트 마스크 solved.ac 티어 silver 3 문제 링크 https://www.acmicpc.net/problem/14889 관련 블로그 포스팅 이 게시글은 코드 플러스 강의 '알고리즘 기초 2/2'의 강의 내용을 기반으로 작성되었습니다. 문제 이해 N 개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제. 즉, 공집합을 제외한 부분 수열을 구해야 하고 부분 수열의 원소를 더한 값이 S가 되는지 확인해야 한다. 문제 접근 N 개의 정수로 이루어진 수열에서 부분 수열 구하기 수열의 부분 수열은 각 원소의 유무로 표현이 가능하다. 수열의 n 번째 원소를 An이라고 했을 때, 부분 수열을 아래와 같이 표..