2003. [Python]수들의 합 2

1. 문제

 

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

 

2. 접근 방법

 

• 시간 제한: 0.5초
• 메모리 제한: 128MB
• 브루트 포스

 

3. 파이썬 코드

 

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

num_list = list(map(int,input().split()))
# M과 같은 값이있을 때 체크하는 변수
cnt = 0
# 합을 나타낼 변수
answer = 0
# 인덱스를 체크할 변수
index = 0
# N 의 길이까지 반복문 반복
for i in range(N):
    # 정답 변수에 num_list 의 값을 더해나감
    answer += num_list[i]
    # 만약 정답이 M 보다 큰 경우
    if answer > M:
        # M보다 작아질 때까지 answer에서 index 값들을 빼준다.
        while answer > M:
            # index가 초기에는 0에 위치해 있고 클 경우 1씩 증가해가며 값들을 빼나간다
            answer -= num_list[index]
            index += 1
        # 만약 값이 같은 경우 cnt 증가
        if answer == M:
            cnt += 1
    # 처음부터 같았을 경우 값 추가
    elif answer == M:
        cnt += 1
print(cnt)

 

4. 문제를 풀고난 후 생각

 

• 문제를 보고 값들을 한번 탐색할 때 더해주고 빼주는 방식을 구현하고 싶었다.
• Index 라는 변수를 선언하여 초기값을 0으로 설정해둔 후 M이라는 기준값보다 커졌을 경우 0번째 인덱스 부터 더해나간 answer 이라는 변수에서 0번 부터 차례대로 M보다 작거나 같아질 때 까지 빼주는 것을 구현하였다.

• 위 그림을 예시로 들어보면 index 값은 0으로 고정되어 있는 상태이고 M보다 answer이 커졌을 경우 while 반복문에 들어가서 M보다 작거나 같을때 행동을 취하게 된다.
• 이렇게 행동을 취하고 난 후 index 값은 1로 증가하게 되며 이후 계속해서 코드가 실행되어 끝났을 때 cnt 값을 출력해주면 답이 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 브루트포스
• 투 포인터