์ค๋ฒ2 : two pointer ๋ฌธ์ ์ด๋ค.
ํ์ด
- ํฌํฌ์ธํฐ๋ i์ด์ j๋ฏธ๋ง์ผ๋ก ์ง ๋ค.
- ๊ฐ์ ๊ฒฝ์ฐ๋ i๋ฅผ ๋๋ ค์ ํ์ ํ๋ค. ์ฆ ์ผ์ชฝ์ด ๋ ๋ง์ด ๋ฐ๋ผ์ค๋ ๊ตฌ์กฐ
- ์ผ๋จ ์ผ์ชฝ์ด ๊ฐ ์ ์์ผ๋ฉด ์ต๋ํ ๋ฐฐ๋ คํด์ฃผ๋ ๋๋
- ๊ทผ๋ฐ ๋ชป๊ฐ, ๊ทธ๋ฌ๋ฉด ์ด์ ์ค๋ฅธ์ชฝ์ด ๊ธฐ์ค์ด ๋์ด์ ํ๋จ
- ์ด์ฐจํผ i, j๊ฐ ๊ฐ์์ง๋ค๋ฉด sum ์ด 0์ด ๋์ด์ j๋ฅผ ๋๋ฆด ์ ๋ฐ์ ์๋ค.
- ๋๊น์ง j๊ฐ ๊ฐ๋๋ฐ, ๊ฐ์ด M๋ณด๋ค ํฌ๋ฉด i๋ฅผ ๋๋ ค๊ฐ๋ฉด์ ํ๋ณด๊ฐ์ด ์๋์ง ํ์ธํด๋ณผ ์ ์๋ค.
- ํ์ง๋ง ๋๊น์ง ๊ฐ๋๋ฐ i์ด์ j๋ฏธ๋ง์ ๊ฐ์ด M๋ณด๋ค ์๋ค๋ฉด ๋์ด์ ๊ฐ๋ฅ์ฑ์ด ์์ผ๋ ์ข ๋ฃํ๋ค.
i์ด์ j๋ฏธ๋ง์ด ์ค์ํ๋ค. ๊ทธ๋ฆฌ๊ณ ๋ง์ง๋ง์ฒ๋ฆฌ๊ฐ ์ค์ํ๋ฐ, ์ด๋ฌํ ๋ถ๋ถ์ ์์ด์ ๋ค์ํ ๊ฒฐ๊ณผ๋ฅผ ์์ํ๊ณ ์์ฝ๋ฉํ๋ ๊ฒ์ด ์ค์ํ๋ค๋ ๊ฒ์ ๋๊ผ๋ค.
์ง๊ธ ๊ฐ์ ๊ฒฝ์ฐ ํ์ ํด๋ณผ ๋งํ ๊ฒ์ด, ๊ฒฐ๊ตญ ๋ง์ง๋ง์ ๋์ฐฉํ์ ๋, ๊ฐ์ด ํฐ ๊ฒฝ์ฐ, ๊ฐ์ ๊ฒฝ์ฐ, ์์ ๊ฒฝ์ฐ์ ๋ํด ํ๋จํด๋ณด๋ฉด ๋๋ค.
Code
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = list(map(int, input().split()))
i, j, ans, bound = 0, 0, 0, 0
while True: # i์ด์ j๋ฏธ๋ง์ bound๋ฅผ ํ์ธํ ๊ฒ์
if bound == m: # ๋จผ์ ์ง๊ธ ๊ฐ์ด ์ ๋ต์ธ์ง ํ์ธ
ans += 1
if bound >= m:
bound -= a[i]
i += 1
elif j == n: # ํน์ i๋ถํฐ j๋ฏธ๋ง๊ฐ๊น์ง ๋ดค๋๋ฐ, j๊ฐ N์ด์ผ. ์ฆ ๋๊น์ง ๊ฐ๊ฑฐ์ง
break # ๊ทผ๋ฐ ๊ฐ์ด ์ด๋ฏธ M๋ณด๋ค ์์, ๊ทธ๋ผ ํ ์ ์๋ ๊ฑด i๋ฅผ ๋๋ฆฌ๋ ๊ฒ ๋ฐ์. ๊ทผ๋ฐ ๊ทธ๊ฑด ๋ฌด์กฐ๊ฑด ์์ง
else:
bound += a[j]
j += 1
print(ans)