[Baekjoon Online Judge] 백준 2003번 수들의 합 2(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2003번 수들의 합 2

(Python)

(글쓴날 : 2020.05.13)

 

---

* Baekjoon Online Judge, 백준 2003번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2003번 수들의 합 2

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

N개의 수로 된 수열이 주어질 때 해당 수열을 조합해 합이 M이 되는 경우의 수를 구하는 문제입니다.

 

저의 경우, 투 포인터를 적용하였으며, Python을 사용했습니다.

문제의 시간제한이 0.5초이므로 시간 복잡도가 O(n²)인 완전 탐색을 구현할 경우 시간 초과가 발생하게 됩니다. 따라서 시간 복잡도가 O(n)인 투 포인터를 적용하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
sP = eP = tot = 0
ans = 0
 
while(True):
    if tot >= M:
        tot -= A[eP]
        eP += 1
    elif sP == len(A):
        break
    else:
        tot += A[sP]
        sP += 1
    
    if tot == M:
        ans += 1
 
print(ans)

---