[C++, Python] 투 포인터 3) BOJ 1806 부분합

https://www.acmicpc.net/problem/1806

1806번: 부분합

풀이

 

합이 특정값 S가 되는 부분 집합의 수를 구하는 문제에서 변형되어 합이 S이상인 부분 집합 중에 원소 개수가 가장 적은 부분집합의 원소 수를 구하는 문제이다. 만족하는 부분 집합이 없으면 0을 출력한다.

 

 

그래서 바뀐 부분이

1) start, end를 움직일때 cnt를 빼고 더해준다.

2) cnt >= mini 이면 start를 움직인다. (이전 문제에서는 sum >= S이면 이었음)

3) sum >= S 이고 cnt < mini일때 mini에 cnt값으로 갱신한다. (이전 문제에선 sum == S이면 cnt++)

1. C++

#include <iostream>
#include <vector>

using namespace std;

int N, S;
vector<int> nums;

void solution() {
	int sum = 0;
	int cnt = 0;
	int start = 0;
	int end = 0;
	int mini = 999999;

	while (true) {
		if (cnt >= mini) {
			sum -= nums[start++];
			cnt--;
		}
		else if (end >= N) break;
		else {
			sum += nums[end++];
			cnt++;
		}

		if (sum >= S && cnt < mini) mini = cnt;
	}
	if (mini == 999999) mini = 0;
	cout << mini << '\n';
}


int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> N >> S;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		nums.push_back(tmp);
	}
	solution();
	return 0;
}

 

 

2. Python

import sys #stdln


def solution(N, S):
    sum = 0
    start =  0
    end = 0
    cnt = 0
    mini = 999999999

    while True:
        if(cnt >= mini) :
            sum -= li[start]
            start += 1
            cnt -= 1
        elif end >= N: break
        else :
            sum += li[end]
            end += 1
            cnt += 1

        if sum >= S and cnt < mini:
            mini = cnt

    if mini == 999999999: mini = 0
    print(mini, '\n')

if __name__ == "__main__":
    N, S = list(map(int, sys.stdin.readline().split()))
    li = list(map(int, sys.stdin.readline().split()))
    solution(N, S)

 

 

다른 투 포인터 문제

백준 온라인 저지 투포인터 문제 목록 

2003 수들의 합2  나의 풀이

1644 소수의 연속합  나의 풀이

1806 부분합 나의 풀이

2143 두 배열의 합  나의 풀이

1728 구슬 굴리기 나의 풀이

2886 Expected Allowance 나의 풀이