백준 1806번 : 부분합(투포인터)

음 leet code trapping rain drop 문제가 이중포인터 카테고리에 있길래 이중 포인터 문제를 더 풀어본다.

 

첫번째 그냥 시간 복잡도 무시하고 생각해보면 왼쪽에서부터 쭉 가면서 거기서 부터 주어진 합을 만들 수 있는 부분 수열인지 알아 보면 된다.

근데 이러면 시간이 너무 오래걸린다.

 

그냥 여기서는 이중포인터로 하래서 생각난 방법인데 어떻게 떠오른지도 모르겠고, 검증을 못하겠다.

좌우끝에서 해당 배열의 총합을 구해놓고 하나씩 빼면서 좌우로 좁혀나가는 것이다.

 

일단 이렇게 좌우로 뺄 수 있으면 막 빼니까 원하는 S가 안만들어진다.

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>

using namespace std;

#define NUM 100001
#define MAXV 987654321
int N, M,S;
int arr[NUM];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> S;

	long long int sum = 0;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	int left=0, right = N-1;

	while (left <= right && sum > S) {
		int bigger, smaller;

		if (sum - arr[left] >= S) {
			sum -= arr[left++];
		}

		if (sum - arr[right] >= S) {
			sum -= arr[right--];
		}
	}

	cout << right - left + 1 << "\n";

	return 0;
}

뭔가 뺄때 조심스럽게 빼야 되는거 같은데 더 큰거 먼저 빼면 되지 않을까??근데 이 생각이 어떻게 나온거지

 

한번 다시 고쳤다. 큰거 먼저 빼고 , 큰거 빼면 sum < S가 되면 반대로 작은쪽을 빼도록 했다..... 근데 예제는 맞는데 

틀렸습니다 뜸 반례를 생각해 보자. 이런 문제는 논리 구조를 왜 이렇게 생각하기 어렵지

#define _CRT_SECURE_NO_WARNINGS
#define debug 0
#include <iostream>
#include <algorithm>
#include <vector>
#include<string.h>

using namespace std;

#define NUM 100001
#define MAXV 987654321
int N, M,S;
int arr[NUM];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	freopen("input.txt", "r", stdin);

	cin >> N >> S;

	long long int sum = 0;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	int left=0, right = N-1;

	while (left <= right && sum > S) {
		int sm_val;
		int b_val;
		int sm_ind,d_l,d_r;
		int d_ol, d_or;

		if (arr[left] > arr[right]) {
			sm_val = arr[left];
			sm_ind = left;

			b_val = arr[right];
			d_l = 1;
			d_r = 0;
			d_ol = 0;
			d_or = -1;
		}
		else {
			sm_val = arr[right];
			sm_ind = right;
			b_val = arr[left];
			d_r = -1;
			d_l = 0;
			d_ol = 1;
			d_or = 0;
		}

		if (sum-sm_val >= S) {
			sum -= sm_val;
			left += d_l;
			right += d_r;
		}
		else {
			sum -= b_val;
			left += d_ol;
			right += d_or;
		}
	}

	cout << right - left + 1 << "\n";

	return 0;
}

반례 찾음; 어쨋든 답을 찾긴 할텐데 가장 짧은 것을 찾는다는 보장은 못한다......

5 5
4 5 2 3 6

 

1번도 잘못 생각한게 해당 위치에서 만들수 있는지만 보면 안되고 만들 수 있고 그중에 가장 짧은것이여야 한다.

5 5
4 2 3 5 6

 

 

원점에서 다시 생각해보자. 내가 구하는건 특정 합을 원하는 가장 짧은 부분 수열이다.

 

어떻게 구할 수 있을까?

 

크게 범위를 잡고 그안에 원하는 연속된 부분합 수열이 있는지 판단하기 어렵다. 일일이 확인해 봐야 알 수 있따.

 

도저히 모르겠어서 이 문제를 참고했다.<https://woovictory.github.io/2019/05/28/Two-Pointer-Algorithm/>

<https://www.acmicpc.net/problem/2003> ;; 근데 풀었던 문제네 심각하다. 문제의 본질을 파악하지 못하고 그냥 배낀거 같다.

 

지금 보니까 띠용했던게, 여러 경우를 다 구한다는 점, 그리고 여전히 1번 방법처럼 그 지점에서 구할 수 있는지 각각 판단해 본다는 점 -> 이 두가지가 절묘하게 투 포인터로 풀린다.... 결국 방법은 1번 방법이랑 동일한 셈이다.

 

내가 막힌 부분은 최소로 되는 배열을 한번에 찾으려 했다. 1번 방법처럼 해보면, 그리고 단번에 찾는다는건 욕심????이라?? 안되는건가..... 어쨋든 여러개 가능한 답중 한개를 찾는다는 사실을 인정하면 1번 방법에서 업그레이드가 가능하다.... 그리고 부분합이라 1번 방법의 시간 복잡도가 1+2+3+....+n이 아니라는 사실도 파악하지 못했다.

 

이렇게 했더니 시간 초과가 발생했다. 일단 또 틀린 부분은 S이상인데 S일때로 생각했따. 이것도 꽤 큰차이가 있을거 같은데? 정확한 S인 부분 수열을 찾는일 이랑 S이상인것중 최소를 찾는거랑 음 비슷한거 같기도.

 

그리고 시간 초과 이유는 나는 결국 O(1)이 아니라 O(n^2)인 풀이였다.

 

구하려는게 명확해야 하는거 같다. 나도 얼추 비슷하게 생각한 것 중에 작게 해서 점차 키워 나가는 방법도 있겠다. 싶었다. 그런데 문제는 어디서 부터 키워나가야 될지 모르겠고 중간 부터 한다 쳐도 좌우로 확장하는 방식만 생각해서 값이 커지기만 하는 방법이였다. 

 

음 아직 연결고리를 잘 못찾겠는데.....

 

약간 이런 직관도 좀 필요한거 같다. 원하는 합을 위해 부분 배열의 양쪽만 좀 조절하면 되지 굳이 처음부터 구할 필요는 없다는 점?