BOJ 백준 2003번 문제 <수들의 합 2> python, 문제 해석 및 풀이

그동안 시간이 없어서 블로그를 잠시 쉬었는데 다시 시작해보려 한다.

(사람들이랑 하는 챌린지는 코드업 기초 100제 중 어려운 문제 풀면서 계속했는데 너무 많이 쉽더라... 백준 실버문제도 안 되는 느낌)

 

오늘 푼 문제는 함께 스터디하는 사람 중 한명이 먼저 푸신 수들의 합 2다.

 

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

---

문제에 대한 간단한 이해

수열이 주어지고 그 수열 안에서 연속적으로 이어지는 부분 수열이 어떤 숫자를 만족하는 경우의 수 구하기입니다.

입출력에 대한 이해

수열의 길이, 만족해야할 숫자, 그리고 수열이 주어집니다.

문제에 대한 세부 이해

1. 주어진 것(입력값)

수열

 

2. 구하고자 하는 것(출력값)

경우의 수

 

3. 규칙

중요한 것은 항상 내부에서 이어져 있어야 한다는 것입니다.

 

- 제약하는 규칙이 있으니 부분 수열안의 모든 숫자를 더해보기 보다는 시간을 줄일 수 있는 방법을 생각해봅니다.

 

- 부분 수열이 변할 때를 생각해본다면 가장 단순한 방법은 항상 앞이나 뒤가 하나씩 변하는 것입니다.

 

- 맨 앞에서부터 시작해 M보다 현재의 부분 수열의 합이 작으면 한 개의 숫자 추가, 크면 한 개의 숫자를 감소시킵니다.

 

구현

- 규칙에 따라서 구현하기 위해 list의 앞 뒤를 정의해줄 front, back의 인덱스와 변했는지 여부를 변수로 만들어줍니다.

 

- 수열을 다 돌 때까지 반복문을 실행시킵니다.

 

- 반복문 안은 변했는지 여부를 통해 갱신해주는 단락과, 현재 합계(cur_sum)와 M을 비교해주는 단락으로 나뉩니다.

 

import sys
from collections import deque

N, M = map(int, (input().split()))

num_list = list(map(int, (input().split())))

front_idx = -1
back_idx = 0
cur_sum = 0
is_front_change = False
is_back_change = True
answer_num = 0

while (back_idx < N) & (front_idx < N):
    # 앞을 땡겼는지 뒤를 밀었는지 확인 후 작업
    if is_front_change:
        # M보다 크면 맨 앞에거 하나 삭제
        cur_sum -= num_list[front_idx]
        is_front_change = False
    if is_back_change:
        # M보다 작으면 맨 뒤 하나 추가
        cur_sum += num_list[back_idx]
        is_back_change = False

    # M과 현재 합 값이 어떤 상태인지 판단
    if M == cur_sum:
        answer_num += 1
        front_idx += 1
        back_idx += 1
        is_front_change = True
        is_back_change = True

    # M보다 크면 맨 앞에거 하나 삭제
    elif M < cur_sum:
        front_idx += 1
        is_front_change = True

    # M보다 작으면 맨 뒤 하나 추가
    else:
        back_idx += 1
        is_back_change = True

print(answer_num)

참고:

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

---

친구가 카드 등록을 도와줬다고 스타벅스 아메리카노를 사줬다...

고마워~

 

(당근 채팅은 꼭 다른 사람에게 부탁하자.)