[BAEKJOON] 1806번 부분합

2024. 4. 16. 22:45·Algorithm/Binary Search

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

 

1806번: 부분합

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

www.acmicpc.net

 

문제조건

 

  1. 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이는?
접근방법

 

시간제한도 타이트하고, 입력값도 크게 주어지길래, 단순히 for문 두번 돌려서 O(n^2) 으로 시간이 걸리게 된다면 당연히 시간초과가 날 것이라고 생각했고, 문득 저번에 이런 비슷한 문제를 푼 경험이 떠올랐다.

2024.03.21 - [Algorithm/구현, 시뮬레이션] - [BAEKJOON] 20922번 겹치는 건 싫어

 

[BAEKJOON] 20922번 겹치는 건 싫어

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원

lsdiary.tistory.com

바로 이 문제다!

투포인터로 대놓고 푸는 문제였다.

예외 사항은 S 이상이 될 수 없는 경우에는 0을 출력하는 것이었는데, 투 포인터에서 S보다 값이 커진적이 한번도 없어서 start값이 갱신되지 않은 경우이다.

 

소스코드
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, s, arr[100001];
int main(){
	cin >> n >> s;
	int res = 100001;
	for(int i = 1; i <= n; i++){
		int a;
		cin >> a;
		arr[i] = a + arr[i-1];
	}
	int start = 1, end = 1;
	while(end <= n){
		if(arr[end] - arr[start -1] < s) end++;
		else {		
			res = min(res, end - start + 1);
			start++;
		}
	}
	if(res == 100001) cout << 0;
	else cout << res;
	
}

'Algorithm > Binary Search' 카테고리의 다른 글

[BAEKJOON] 1348번 주차장  (0) 2024.06.01
[BAEKJOON] 2568번 전깃줄 - 2  (0) 2024.03.30
[BAEKJOON] 19637번 IF문 좀 대신 써줘  (0) 2024.03.25
[BAEKJOON] 2613번 숫자구슬  (1) 2024.03.16
[BAEKJOON] 6236번 용돈 관리  (3) 2024.03.14
'Algorithm/Binary Search' 카테고리의 다른 글
  • [BAEKJOON] 1348번 주차장
  • [BAEKJOON] 2568번 전깃줄 - 2
  • [BAEKJOON] 19637번 IF문 좀 대신 써줘
  • [BAEKJOON] 2613번 숫자구슬
Ls._.Rain
Ls._.Rain
안되면 될때까지 삽질했던 기록
  • Ls._.Rain
    Ls{Diary}
    Ls._.Rain
  • 전체
    오늘
    어제
    • 분류 전체보기 (136)
      • Github (2)
      • Spring (51)
        • Batch Programming (13)
        • 결제 (4)
        • 대용량 트래픽 (32)
        • OpenAI (0)
        • Security (0)
        • WebSocket (0)
        • JPA (1)
      • Algorithm (67)
        • DFS (6)
        • BFS (6)
        • Dynamic Programming (10)
        • Brute Force (4)
        • Binary Search (6)
        • 구현, 시뮬레이션 (15)
        • Stack (1)
        • Greedy (4)
        • Priority_Queue (2)
        • Back Tracking (3)
        • Geometry (2)
        • SCC (1)
        • 투포인터 (4)
        • 최대유량 (1)
        • 정렬 (1)
      • OS (0)
      • DevOps (15)
        • AWS (11)
        • Docker (4)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • hELLO· Designed By정상우.v4.10.0
Ls._.Rain
[BAEKJOON] 1806번 부분합
상단으로

티스토리툴바