문제 출처
https://www.acmicpc.net/problem/1208
1208번: 부분수열의 합 2
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
접근 방식 및 풀이
- 1182와 비슷한 문제라고 생각하는 순간 해맨다. -> 같은 알고리즘을 쓰면 시간 초과 발생
- 여러 블로그들을 참고하여 배열의 크기가 크기때문에, 배열을 반으로 나눠 각각 부분합들을 구해준 후 투포인트 알고리즘으로 해결하라는 힌트를 받았다.
[백준 알고리즘]1208번 부분수열의 합2
백준 알고리즘 부분수열의 합 2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 5710 1086 693 20.798% 문제 N개의 정수로 이루어진 수열이 있을 때, 길이가 양수인 부분수열 중에서 그 수열의..
kohen.tistory.com
- 부분합이 S인 결과값을 count할 때 int타입 / long 타입 설정하는거에 너무 해매서 .... 포기할뻔 했던 문제..
소스 코드
결과
'Competition > Baekjoon' 카테고리의 다른 글
| [백준] 10819번 자바 차이를 최대로 (0) | 2020.04.29 |
|---|---|
| [백준] 6603번 자바 로또 (0) | 2020.04.27 |
| [백준] 5014번 자바 스타트 링크 (0) | 2020.04.25 |