C++ [백준]1806번 부분합

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

1806번: 부분합

 

 

솔루션

---

처음에 이 문제를 보고 dp인가? 싶었으나 도저히 아닌 것 같아서 알고리즘 보기를 하니, 투 포이터였다..

투 포인터를 보고 나니, 바로 방법이 생각이 났다.

 

i) 시작점과, 끝점의 idx를 만들고, idx 사이의 값들을 더해 놓는다.

ii) 값이 작다면, 끝 idx를 증가시키고, 값을 더한다.

iii) 값이 크다면, 더 작아져도 되므로 시작점 idx를 증가 시키고 값을 빼 준다.

iv) 끝 점의 idx가 N을 넘어가면 더이상 반복문을 탈출한다.

 

코드

---

#define LL long long int
#include <iostream>
using namespace std;

int value[100005];

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

	int N, dest;
	cin >> N >> dest;

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

	int str = 0, end = 1;
	int temp = value[0];
	int min = 987654321;
	while (true) {

		if (temp >= dest) {
			//만약 그 수라면, 수열의 길이 비교.
			if (min > end - str) {
				min = end - str;
			}
			if (end - str == 1) {
				temp += value[end++];
			}
			temp -= value[str++];
		}
		else {
			//수열의 수를 만족하지 못했다면.
			//어떠한 수를 빼거나, 더해야하 함.

			//만약 수를 더해야 하는 경우라면,
			if (temp < dest) {
				temp += value[end++];
			}
			else if (temp > dest ) {
				//만약 수를 빼야 하는 경우라면,
				//str이 end와 같아지면 안됨..
				if (end - str == 1) {
					temp+=value[end++];
				}
				temp -= value[str++];
			}
		}
		//end가 끝에 왔는데,
		if (end > N) {
			break;
		}
		//end가 끝이고, str도 끝일때,
		if (end > N && str >= N) {
			break;
		}

	}
	if (min == 987654321) {
		min = 0;
	}
	cout << min << "\n";
	return 0;
}

처음에 값이 같아야 min이 돌아가도록 했는데, 문제를 다시 잘 읽어보니,

합이 그 이상인 것을 고르라고 해서 다시 수정을 해서 맞췄습니다를 받았다.