[백준/C++/JS] 1806번. 부분합

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

1. 문제

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

2. 입력

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

3. 출력

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

4. 풀이

• 투 포인터 문제
• start와 end 두 개의 포인터를 조작해서 답을 찾는다.
• start부터 end까지 합이 원하는 결과보다 작다면 end를 증가시킨다.
  • start부터 end까지 합을 구할 때 갱신할 때마다 새로 더하지 말고 현재의 합계를 저장해놓고 start에 해당하는 값을 빼거나 end에 해당하는 값을 더하는 식으로 진행하는 게 효율적이다.
  • 주의할 점은 start를 증가시킬 때는 해당하는 값을 먼저 빼고 인덱스를 증가시켜야 하고 end는 인덱스를 증가시키고 값을 더해야 한다.
• start부터 end까지 합이 원하는 결과 이상이면 현재 길이를 저장한다.
  • 현재 길이가 최솟값일 때만 결과를 갱신한다.
• start나 end 중 하나가 배열의 범위를 벗어나면 반복문을 종료한다.

5. 처음 코드와 달라진 점

• 부분합이 이상인 것을 일치로 봐서 코드를 수정했다.
• result 값을 n으로 초기화했는데 이러면 답을 찾았는지 아닌지 확인할 방법이 없어서 boolean 타입 변수 findAnswer를 추가해주었다.
• findAnswer 없이 result 값을 n 이상의 큰 값으로 지정해주어도 될 것 같다.

6-1. 코드(findAnswer 有)

#include <iostream>
#include <algorithm>

using namespace std;

int n, target;
int arr[100000];

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

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

  int start = 0, end =0;
  int sum = arr[start];
  int result = n;
  bool findAnswer = false;

  while (start < n && end < n) {
    if (target <= sum) {
      findAnswer = true;
      result = min(result, end - start + 1);
      sum -= arr[start];
      start++;
    }
    else {
      end++;
      sum += arr[end];
    }
  }
  if (!findAnswer) cout << 0;
  else cout << result;
}

6-2. 코드 (INF 이용)

#include <iostream>
#include <algorithm>
#define INF 987654321

using namespace std;

int n, target;
int arr[100000];

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

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

  int start = 0, end =0;
  int sum = arr[start];
  int result = INF;

  while (start < n && end < n) {
    if (target <= sum) {
      result = min(result, end - start + 1);
      sum -= arr[start];
      start++;
    }
    else {
      end++;
      sum += arr[end];
    }
  }
  if (result == INF) cout << 0;
  else cout << result;
}

21.10.11 추가

풀이

• 기본 풀이는 같지만 while-loop에서 for-loop로 변경하였다.
• answer 변수를 INF 값으로 초기화한다.
• 반복문을 돌면서 sum 변수에 right 인덱스의 값을 추가한다.
• sum 변수의 값이 s보다 크거나 같다면 작아질 때까지 아래의 작업을 반복한다.
  • right - left + 1의 값과 answer 값 중 작은 값으로 answer의 값으로 갱신한다.
  • while 반복문을 돌면서 left에 해당하는 값을 빼준다.
• for 반복문이 끝나고 answer가 여전히 INF값이면 0으로 갱신한다.
• answer에 저장된 값을 출력한다.

코드 - CPP

#include <iostream>
#include <algorithm>
#define INF 987654321

using namespace std;

int nums[100000];
int n, s;

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

  int answer = INF;
  int sum = 0;
  cin >> n >> s;

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

  int left = 0;
  for (int right = 0; right < n; right++)
  {
    sum += nums[right];

    while (s <= sum)
    {
      answer = min(answer, right - left + 1);
      sum -= nums[left++];
    }
  }

  answer = answer == INF ? 0 : answer;
  cout << answer;
}

코드 - js

function solution(nums, s) {
  let answer = Number.MAX_SAFE_INTEGER;
  let sum = 0;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (s <= sum) {
      answer = Math.min(answer, right - left + 1);
      sum -= nums[left++];
    }
  }
  answer = answer === Number.MAX_SAFE_INTEGER ? 0 : answer;
  return answer;
}