티스토리 뷰
크기가 양수인 부분수열의 모든 원소의 합이 S가 되는 경우를 구하는 문제이다.
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
위 문제와 유사한 풀이로 해결이 가능하다.
하지만 부분 수열의합1의 최대 크기가 2^20인데 반해 부분수열의 합2은 최대 크기가 2^40이다. 따라서 시간복잡도를 줄일 방법이 필요하다.
시간복잡도를 줄이기위해 배열을 반으로 나눌 수 있다. 반으로 나눈다면 각 배열의 최대 크기는 2^20이 되고 최종적으로 최악의 시간 복잡도는 2^21이 되어 시간복잡도가 거의 절반으로 줄어든다.
배열을 반으로 나눈 뒤에는 투 포인터(left, right)를 사용하여 이분탐색을 수행하면 문제를 해결할 수 있다.
Python
Java
728x90
'PS > 백준' 카테고리의 다른 글
| [백준] 1436 영화감독 숌 (0) | 2021.04.15 |
|---|---|
| [백준] 1450 냅색문제 (0) | 2021.04.12 |
| [백준] 2632 피자 판매 (0) | 2021.04.11 |
| [백준] 1253 좋다 (0) | 2021.04.11 |
| [백준] 17825 주사위 윷놀이 (0) | 2021.04.06 |
댓글