파이썬 알고리즘 015 | 수들의 합 ***복습꼭

15. 수들의 합

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의
합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

▣ 입력설명
첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …,
A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

▣ 출력설명
첫째 줄에 경우의 수를 출력한다.

▣ 입력예제 1
8 3
1 2 1 3 1 1 1 2

▣ 출력예제 1
5

<내 풀이>

풀지 못했다..

<풀이>

풀이에 대한 설명:

우선 합이 m보다 작으면 합의 범위가 늘어나야 하므로
rt번째의 값까지 더해주고(rt는 초기값이 이미 lt보다 하나 큰 상태)
rt는 한 칸 오른쪽으로 움직인다.
런데 rt가 무한히 커질 수는 없으므로 수열의 개수보다 커지면 break로 빠져나온다.

또한 위에서 설명했던 것처럼 일정 범위 이상의 합은 구할 필요가 없으므로, lt에서 시작한 뒤 rt까지의 합이 m보다 크면 그 다음부터는 합에서 lt 위치의 값을 빼고 lt는 한 칸 오른쪽으로 옮겨준다.

그리고 lt와 rt의 값이 같아지는 경우(=겹치는 경우)는 결국 그 자리의 숫자만 합에 들어가는 것 뿐, 그 합에 따라 다음 움직임이 결정된다.
lt는 합이 커질 때만 오른쪽으로 움직이므로, lt가 rt보다 커지는 경우는 없다.

<풀이>

n, m = map(int,input().split())
a=list(map(int,input().split()))
cnt=0
lt=0
rt=1
tot=a[0] #range(lt,rt)의 부분합

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)

<반성점>

• 하나도 못 풀어냈다.. 반드시 꼭 다시 풀어보자

<배운 점>

• • python 반복문 탈출

(1) break
-while의 무한루프에서 숫자를 증가시키다가 변수i가 일정이 되면 반복문을 끝낼 수 있다

i = 0
while True:    # 무한 루프
    print(i)
    i += 1          # i를 1씩 증가시킴
    if i == 100:    # i가 100일 때
        break       # 반복문을 끝냄. while의 제어흐름을 벗어남

-for의 무한루프에서도 반복문을 끝낼 수 있다

for i in range(1000):
	print(i)
    if i==100
    	break

(2) continue

-while 에서 코드 실행 건너뛰기

i = 0
while i < 100:        # i가 100보다 작을 때 반복. 0부터 99까지 증가하면서 100번 반복
    i += 1            # i를 1씩 증가시킴
    if i % 2 == 0:    # i를 2로 나누었을 때 나머지가 0이면 짝수
        continue      # 아래 코드를 실행하지 않고 건너뜀
    print(i)

-for에서 코드 실행 건너뛰기

for i in range(100):       # 0부터 99까지 증가하면서 100번 반복
    if i % 2 == 0:         # i를 2로 나누었을 때 나머지가 0면 짝수
        continue           # 아래 코드를 실행하지 않고 건너뜀
    print(i)

<2회독 내 풀이>

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

for i in range(n):
    sum=a[i]
    if sum==m:
        cnt+=1
        continue
    for j in range(i+1,n) :
        sum+=a[j]
        if sum==m:
            cnt+=1
            break
print(cnt)

• 풀이 과정을 기억하지 못하고 이중 for문으로 풀었다