수들의 합

 

N개의 수로 된 수열 A[1], A[2], ..., A[N]이 있을 때,

이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+...+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램 작성

첫 줄에 N 과 M이 주어지고

두번째 줄에 수열이 주어짐

 

입력예시)

8 3

1 2 1 3 1 1 1 2

 

출력예시)

5

---

내가 쓴 코드

import sys
sys.stdin = open("input.txt", 'rt')

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

sum = 0
cnt = 0

for i in range(N):
    sum = lst[i]
    if sum == M:
        cnt += 1
        continue
    elif sum > M:
        continue

    for j in range(i+1, N):
        sum += lst[j]
        if sum == M:
            cnt += 1
            continue
        elif sum > M:
            continue

print(cnt)

 

모범답안

import sys
sys.stdin = open("input.txt", 'rt')

n, m = map(int, input().split())
a = list(map(int, input().split()))

lt = 0
rt = 1
tot = a[0]
cnt = 0

while True:
    if tot < m:
        if rt < n:
            tot += a[rt]
            rt += 1
        else:
            break
    elif tot == m:
        cnt += 1
        tot -= a[lt]
        lt += 1
    else:
        tot -= a[lt]
        lt += 1

print(cnt)

 

모범답안 보고 느낀점

1. 나와 비슷하면서 다른 답안...

 

2. 인덱스를 가리키는 포인터를 구현하는접근방식을 자주 쓰는 듯하다..

나도 익숙해져야지!!!

 

3. 좌측인덱스(시작인덱스)를 가리키는 lt, 우측인덱스(끝인덱스)를 가리키는 rt

초기 total = list[0]

 

total < M: total에 rt가 가리키는 값 더하기, rt를 1 증가

total = M: cnt 1 증가, total에서 lt가 가리키던 값을 빼주고 lt를 증가시킴, 그리고 total은 다시 Lt가 가리키는 값

total > M: total에서 lt가 가리키던 값을 빼주고 lt를 증가시킴, 그리고 total은 다시 lt가 가리키는 값

---

다시 써보기

import sys
sys.stdin = open("input.txt", 'rt')

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

total = lst[0]
cnt = 0

lt = 0
rt = 1

while True:
    if total < M:
        if rt < N:
            total += lst[rt]
            rt += 1
        else:
            break
    elif total == M:
        cnt += 1
        total -= lst[lt]
        lt += 1
    else:
        total -= lst[lt]
        lt += 1

print(cnt)