[BOJ알고리즘, C++]#1806_부분 합, Prefix Sum, 누적 합, 투 포인터

2024. 3. 3. 10:53· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 누적 합, Prefix Sum
  4. 2. 투 포인터 알고리즘
  5. 3. 누적 합을 저장하고, 투 포인터를 활용해 가장 짧은 구간을 찾습니다.
  6. #3. 코드

 

#1. 문제

 

1806번: 부분합

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

www.acmicpc.net

 


 

#2. 풀이

 

1. 누적 합, Prefix Sum

 

[BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘

[BOJ 알고리즘, C++] #11659_구간 합 구하기 4, Prefix Sum(누적 합) 알고리즘 BOJ 알고리즘 문제 풀이, 11659_구간 합 구하기 4 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 과정 위 문

webddevys.tistory.com

 

Prefix Sum 알고리즘은 수열의 시작점부터 마지막까지의 누적합을 배열에 저장하고, 각 구간의 합을 arr [right] - arr [left-1]로 계산하는 알고리즘입니다.

 

2. 투 포인터 알고리즘

 

[알고리즘]#7_투 포인터

#1. 개념 1. 투 포인터 [정의] : '투 포인터' 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. [특징] : '투 포인터' 알고리즘은 일반적으로 정렬된 배열

webddevys.tistory.com

 

투 포인터 알고리즘은 두 개의 포인터를 활용해 정렬된 배열에서 조건을 만족하는 부분 배열을 찾는 알고리즘입니다. 두 개의 포인터를 같은 방향 혹은 다른 방향으로 움직이며 찾고자 하는 구간의 범위를 넓히거나 좁히며 조건을 만족하는 부분 배열을 찾습니다.

 

3. 누적 합을 저장하고, 투 포인터를 활용해 가장 짧은 구간을 찾습니다.

 

  1. 먼저, 입력 받은 정수의 누적합을 저장합니다.
  2. 두 개의 포인터를 정렬된 배열의 시작점으로 초기화합니다. 
  3. 주어진 S값과 구간 합을 비교하며, 구간 합이 S와 같거나 클 경우 왼쪽 포인터를 오른쪽으로 이동시킵니다. 반대로, 구간 합이 S보다 작을 경우, 오른쪽 포인터를 오른쪽으로 이동시킵니다.

 


 

#3. 코드

 

/*
    @문제 : 부분 합이 S가 되는 최소 길이
    @설명
        1. Prefix Sum + 투 포인터 활용
        2. left와 right를 같은 위치에서 출발 시킨다.
        3. 만약, left == right 일때, Sum이 S와 크거나 같을 경우, left를 증가시킵니다.
        4. 만약,
*/

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

typedef long long ll;

int N;
ll S;
vector<ll> prefixSum;

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

    cin >> N >> S;

    prefixSum.resize(N, 0);

    for (int i = 1; i <= N; ++i)
    {
        int tmp;
        cin >> tmp;

        prefixSum[i] = prefixSum[i - 1] + tmp;
    }

    int left = 1;
    int right = 1;
    int minDist = INT_MAX;
    while (left <= right && right <= N && left <= N)
    {
        ll sum = prefixSum[right] - prefixSum[left - 1];
        if (sum >= S)
        {
            minDist = min(minDist, right - left + 1);
            left++;
        }
        else
        {
            right++;
        }
    }

    if (minDist != INT_MAX)
        cout << minDist;
    else
        cout << 0;

    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#2493_탑, 스택, 히스토그램 유형  (0) 2024.03.07
[BOJ알고리즘, C++]#9375_패션왕 신해빈, um, 경우의 수  (0) 2024.03.07
[BOJ알고리즘, C++]#15681_트리와 쿼리, 트리, DFS, DP  (0) 2024.03.03
[BOJ알고리즘, C++]#2533_사회망 서비스, 트리, DP  (1) 2024.03.03
[BOJ알고리즘, C++]#9095_1, 2, 3 더하기, DP  (0) 2024.03.03
  1. #1. 문제
  2. #2. 풀이
  3. 1. 누적 합, Prefix Sum
  4. 2. 투 포인터 알고리즘
  5. 3. 누적 합을 저장하고, 투 포인터를 활용해 가장 짧은 구간을 찾습니다.
  6. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#2493_탑, 스택, 히스토그램 유형
  • [BOJ알고리즘, C++]#9375_패션왕 신해빈, um, 경우의 수
  • [BOJ알고리즘, C++]#15681_트리와 쿼리, 트리, DFS, DP
  • [BOJ알고리즘, C++]#2533_사회망 서비스, 트리, DP
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 디자인 패턴
  • 알고리즘
  • Unreal Blueprint
  • set
  • C++
  • 그래프
  • BOJ
  • 트리
  • 정렬
  • 최단 경로
  • programmers
  • stl
  • 기술 질문
  • 개발
  • Effective C++
  • 우선순위 큐
  • unreal
  • DP
  • BFS
  • dfs

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#1806_부분 합, Prefix Sum, 누적 합, 투 포인터
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.