백준 2015[수들의 합 4]

1. 문제 설명

문제 URL: https://www.acmicpc.net/problem/2015
이 문제는 주어진 수열에서 연속된 부분 수열의 합이 특정 값  K 가 되는 경우의 수를 찾는 문제입니다. 수열의 각 요소는 정수로 이루어져 있으며, 연속된 부분 수열을 선택했을 때 그 합이 정확히  K 가 되는 경우의 수를 구해야 합니다. 문제를 해결하기 위해 누적합을 활용하여 각 부분 수열의 합을 계산하고, 딕셔너리를 이용해 빠르게 결과를 구할 수 있습니다.

2. 정답 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())  # 수열의 길이 N과 목표 합 K를 입력받음
A = list(map(int, input().split()))  # 수열 A 입력받기

# 누적합 배열 dp를 생성. dp[i]는 A의 첫 번째 원소부터 i번째 원소까지의 합
dp = [0] * (N + 1)
for i in range(N):
    dp[i+1] = A[i] + dp[i]  # dp[i+1]에 A[i]를 더해 누적합을 저장

ans = 0  # 합이 K가 되는 부분 수열의 개수를 저장할 변수
cnt = {}  # 각 누적합의 빈도를 저장할 딕셔너리

# 누적합을 순회하며 합이 K가 되는 부분 수열의 개수를 계산
for i in range(1, N+1):
    if dp[i] == K:
        ans += 1  # dp[i] 자체가 K일 때, 부분 수열이 A의 처음부터 i까지의 구간인 경우

    # 현재 누적합 dp[i]에서 K를 뺀 값이 이전에 등장한 적이 있다면,
    # 그 경우의 수만큼 부분 수열의 합이 K가 되는 경우가 존재함
    if dp[i] - K in cnt:
        ans += cnt[dp[i] - K]

    # 현재 누적합 dp[i]의 빈도를 딕셔너리에 추가하거나 증가시킴
    if dp[i] in cnt:
        cnt[dp[i]] += 1
    else:
        cnt[dp[i]] = 1

# 최종적으로 합이 K가 되는 부분 수열의 개수를 출력
print(ans)

3. 코드 설명

1) 시작 (Start)

• 프로그램이 시작됩니다.

2) 입력 받기

• 수열의 길이 N과 목표 합 K를 입력받습니다.
• 수열 A를 입력받습니다.

3) 누적합 배열 초기화

• 누적합 배열 dp를 길이 N+1로 초기화합니다. 모든 요소는 0으로 초기화됩니다.
• 변수 ans(부분 수열의 합이 K인 경우의 수)와 cnt(누적합의 빈도 딕셔너리)를 초기화합니다.

4) 누적합 계산

• 수열 A의 각 요소에 대해, dp 배열을 업데이트하여 누적합을 계산합니다.
• dp[i+1] = A[i] + dp[i]로 현재 위치까지의 누적합을 저장합니다.

5) 부분 수열 합 계산

• i를 1부터 N까지 반복하여:
• 현재 누적합 dp[i]가 K와 같다면, ans를 1 증가시킵니다.
• dp[i] - K가 cnt에 존재한다면, 그 값을 ans에 더해줍니다. 이는 dp[i] - K로 끝나는 부분 수열들이 모두 K가 되는 부분 수열임을 의미합니다.
• 현재 누적합 dp[i]의 빈도를 cnt에 추가하거나, 이미 있다면 그 빈도를 증가시킵니다.

6) 결과 출력

• 계산된 ans를 출력합니다. 이는 합이 K가 되는 부분 수열의 개수입니다.

4. Github으로 확인

coTest/BOJ_EASY/E_BOJ_19_2015.py at main · pcy4196/coTest