.PNG)
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문으로 풀었다
