본문 바로가기

부분수열의 합1

[백준 14225] 부분수열의 합, C++ https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 � www.acmicpc.net 본 문제는 주어진 수열의 부분수열을 구하고 구한 부분수열의 합을 구하는 문제다. 문제를 해결하기 위해 2가지의 과정이 필요하다. 1. 모든 부분수열의 합을 구한다. 2. 1.에서 구만 합을 저장한다. 위의 과정마다 각각 2가지 방법이 떠올랐다. 1.을 해결하기 위해서는 비트 마스크를 이용하여 모든 경우의 수를 찾는 방법과 재귀.. 2020. 9. 27.

티스토리툴바