이 영역을 누르면 첫 페이지로 이동
hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

페이지 맨 위로 올라가기

hoonDEV

BOJ 2003 - 수들의 합 2 문제풀이

  • 2020.04.19 20:50
  • 알고리즘/문제풀이

문제를 읽고 이해하기

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

재정의와 추상화

대표적인 투 포인터 알고리즘(Two Pointers Algorithm) 문제이다. 정말 딱 투 포인터 알고리즘만 쓰면 풀리는 문제.

알고리즘 배우기

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window)

 

투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09)

조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 번째로 소개해드릴 기법은 투 포인터(tw...

blog.naver.com

관련 문제

2020/04/19 - [알고리즘/문제풀이] - BOJ 1806 - 부분합 문제풀이

 

BOJ 1806 - 부분합 문제풀이

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

hoondev.tistory.com

코드 작성

#include <iostream>
using namespace std;

int A[10000];

int main() {
    int n, m, ans = 0;
    cin >> n >> m;

    for (int i = 0; i < n; i++) cin >> A[i];

    int s = 0, e = 0, psum = 0;
    while (1) {
        if (psum >= m) psum -= A[s++];
        else if (e == n) break;
        else psum += A[e++];

        if (psum == m) ans++;
    }
    cout << ans;
    return 0;
}

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

BOJ 1202 - 보석 도둑 문제풀이  (0) 2020.04.20
BOJ 10942 - 팰린드롬? 문제풀이  (0) 2020.04.19
BOJ 1806 - 부분합 문제풀이  (0) 2020.04.19
BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이  (0) 2020.04.19
BOJ 1074 - Z 문제풀이  (0) 2020.04.18

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • BOJ 1202 - 보석 도둑 문제풀이

    BOJ 1202 - 보석 도둑 문제풀이

    2020.04.20
  • BOJ 10942 - 팰린드롬? 문제풀이

    BOJ 10942 - 팰린드롬? 문제풀이

    2020.04.19
  • BOJ 1806 - 부분합 문제풀이

    BOJ 1806 - 부분합 문제풀이

    2020.04.19
  • BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이

    BOJ 12015 - 가장 긴 증가하는 부분 수열 2 문제풀이

    2020.04.19
다른 글 더 둘러보기

정보

hoonDEV 블로그의 첫 페이지로 이동

hoonDEV

  • hoonDEV의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그

카테고리

  • 분류 전체보기 (91)
    • 일상 (13)
      • 후기 (1)
      • 계획 (11)
    • 공지사항 (1)
    • 알고리즘 (54)
      • 문제풀이 (53)
      • 이론 (1)
    • 공부 (19)
      • React (0)
      • Angular (5)
      • Java (3)
      • C, C++ (3)
      • JavaScript (6)
      • WEB (2)
    • 디자인 (1)
      • UI, UX (1)
    • 개발 (0)
      • boom (0)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • dp
  • es6
  • 알고리즘
  • javascript
  • 그리디
  • 문제풀이
  • 백준
  • 이분탐색

나의 외부 링크

정보

훈개발자의 hoonDEV

hoonDEV

훈개발자

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. © 훈개발자. Designed by Fraccino.

티스토리툴바