뚝딱뚝딱

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

💡 부분합

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

입력예시
10 15
5 1 3 5 10 7 4 9 2 8

출력예시
2

✅ 문제 풀이

부분합이라고 해서 무조건 크기가 N인 배열에 누적합을 구해 놓으면 해결될 문제가 아니다.

이 문제에서 핵심은 "한번만" 순회하여 해결해야 한다는 것이다.

처음에는 for문 안에 부분 while문을 넣어서 결론적으로는 o(n^2)의 시간복잡도로 구현하였다. 결과는 역시 시간초과였다.

부분합 문제는 특히 o(n)으로 해결해야 한다.

그럼 어떻게 해결할 수 있을까?

문제를 풀면서 인지하고 있었던 것은, 앞에서부터 누적해 나가되, 그 값이 S이상이 되면 멈추는 것이다. 그리고 다시 앞에서부터 하나씩 줄여갔을 때에도 여전히 S이상이라면 이전 보다는 더 짧은 길이가 될 수 있다는 점이다.

그러면 여기서 알 수 있는 점은, 시작 점과 끝점을 가리키는 두개의 포인터가 필요하다는 것이다.

우리는 그것을 st, en이라고 할 것이다. 그리고 그 값은 각각 1부터 시작한다.

그리고 부분합을 가리키는 total을 선언하고, st와 en이 현재 1을 가리키므로, total은 수열의 1번째 값을 갖도록 한다.

answer는 최소 길이인데, 현재 수열의 최대 값은 100000이기 때문에, 초기값을 100001로 설정하여 min값을 찾아가도록 한다.

이제 while문을 통해 수열을 순회하는데, 시작점인 st는 끝점인 en보다는 작거나 같아야 하며, en이 N과 같아질 때까지 순회하도록 한다.

그리고 아래의 조건에 따라 수행한다.

만약 현재 total이 S보다 크다면, 조건을 만족한 것이므로, 현재의 answer값 (st-en+1)=현재 total을 이루는 길이를 비교해서 더 작은 값으로 answer를 갱신한다.

만약 total이 S보다 작다면, en을 하나 늘려서 다음 값을 total에 누적해주고, total이 S보다 크다면, total에서 st가 가리키는 값을 빼준 후 st를 하나 줄여준다.

=> 이렇게 되면, st를 줄였을 경우에도 total이 S조건보다 커서 answer가 더 작은 값으로 갱신될 수 있기 때문에, 이런식으로 한번의 순회로 답을 찾아갈 수 있는 것이다.

순회가 끝나고 난뒤에는, answer가 초기값 100001이 아니라면 한번이라도 S보다 큰 부분합이 있었다는 것이므로 answer를 출력하고, answer가 초기값 그대로였다면, S보다 큰 부분합이 없었다는 것이므로 0을 출력하도록 한다.

전체코드는 아래와 같다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

	int N, S;
	cin >> N >> S;

	vector<int> vec(100001, 0);

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

	int answer = 100001;
	int total = vec[1];//첫번째 값부터 담아서 시작
	int st = 1;//시작 포인터
	int en = 1;//끝 포인터

	while (st <= en && en <= N) {
		if (total >= S) answer = min(answer, en - st + 1);
		if (total < S) {
			en++;
			total += vec[en];
		}
		else {
			total -= vec[st];
			st++;
		}
	}

	if(answer!=100001) cout << answer;
	else cout << 0;

	return 0;
}

소프티어에 있는 lv3 연습 문제 "성적 평균"에 대한 풀이 방법이다.

풀이 날짜는 2023.11.01로, 최근에 소프티어 페이지가 리뉴얼 되었다.

그런데 리뉴얼 후 문제인지, 아니면 이렇게 업데이트 된 것인지 모르겠는데..

어제 다른 문제를 풀 때, 답이 틀리면, 제출 이력에 틀린 답도 뜨고, 왜 틀렸는지(그 문제의 경우 시간초과였음) 표시도 되어있었다.

그런데 오늘 아침부터 풀고 있던 이문제.. 문제 자체에만 틀렸다고 표시되어 있고, 내가 제출한 이력은 전혀 보이지 않는다.

분명 예시 테케도 맞았고, 혹시나 하여 다른 사람들의 풀이랑 내 풀이도 비교해보았는데, 접근 방식이 동일하다.

그런데, 제출만하여 계속 틀렸다고만 뜨고, 제출 이력에는 표시조차 되어 있지 않다. 왜 틀렸는지는 알려줘야지....

거의 20번은 넘게 제출을 한 것 같은데.. 그래서 일단 개발자 톡에 문의를 넣어놓았고, 내 풀이상의 문제일 수 도 있을것 같아 코드도 함께 게시해 놓았다.

부분합 사용

이 문제는 부분합을 사용하면 아주 쉽고 간단하게 풀이할 수 있다.

부분합??

예를 들어서 5명의 학생이 있고, 각각의 점수는 20, 40, 10, 80, 30 이라고 하자.

그러면 크기가 5인 배열에 1명까지 더한 값, 2명까지 더한 값...이렇게 저장하는 것이다.

즉 arr이라는 크기가 5인 배열이 있으면

arr[0] =20

arr[1] = 20+40 = arr[0]+40

arr[2] = 20+40+10 = arr[1]+10

...

이렇게 이전에 저장해둔 값에 새로운 값을 추가로 저장해 총합을 구해 가는 것이다.

배열의 인덱스는 학번과도 같고(문제에서는 1부터 시작하지만, 예시로는 0부터 해도 무방), 만약 1번 학생부터 3번 학생까지의 점수 평균을 구한다면..

3번학생까지의 부분합-0번학생까지의 부분합 = 1번 학생부터 3번학생까지의 점수 합

이기 때문에, 구간이 주어지면 이미 구해진 합을 이용해 구간 합을 쉽게 구할 수 있다.

그리고 1번 학생부터 3번 학생까지 니까 (3-1+1)로 나누어 주면 평균은 바로 구할 수 있다.

따라서 아래와 같은 순서로 진행한다.

1. 학생 수인 N과 구간 수인 K를 먼저 받아서 저장한다.

2. 1부터 i번(1<=i<=N)까지의 학번을 갖는 학생 들의 점수 합을 저장하는 크기가 N+1인 벡터(또는 배열)를 생성한다 => 0번은 0으로 초기화 할 것이다.

3. 입력으로 학생들의 점수를 받을 때, 벡터에 합을 저장해준다.

4. 입력으로 K개의 구간 정보를 입력 받을 때, 앞에서 구한 부분합을 이용해서 평균을 바로 출력한다.

전체 코드는 아래와 같다.

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
  int N,K;
  
  cin>>N>>K;

  vector<double> prefixSum(N+1);

  prefixSum[0]=0;
  
  for(int i=1; i<N+1; i++){
    int S;
    cin>>S;
    prefixSum[i] = prefixSum[i-1]+(double)S;
  }

  int A,B;
  for(int i=1; i<K+1; i++){
    cin>>A>>B;
    printf("%.2f\n", (double)(prefixSum[B]-prefixSum[A-1])/(double)(B-A+1));
  }

  return 0;
}

다른 사람들의 코드랑 비교해보아도, 이상이 없, 예제도 통과하는데, 틀린 이유를 모르겠으나.. 일단은 올려둔다.

예외를 발견한다면 알려주세요!!!