-
백준(BOJ) 14225번 부분수열의 합알고리즘 풀이/백준(Boj) 2019. 10. 25. 02:42
문제 : 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)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.
www.acmicpc.net
풀이 :
S의 최대 크기는 20 이고 한 숫자당 10만이하 이니 합에 최대값은 20 * 100000일것이다. 이 배열을 잡은 후에
재귀호출을 통해서 각 부분 수열을 더하거나 지나치거나 하여 모든 경우의 수를 체크해주자. 그 후
1부터 시작해서 값이 false라면 종료한다.
코드 ( C++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 1937번 욕심쟁이 판다 (31) 2019.10.27 백준(BOJ) 2169번 로봇 조종하기 (3) 2019.10.27 백준(BOJ) 2151번 거울 설치 (31) 2019.10.22 백준(BOJ) 2422번 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (31) 2019.10.18 백준(BOJ) 4연산 (31) 2019.10.16