[BOJ] 2003번: 수들의 합 2

1일 1알고리즘 공부 중 오늘의 알고리즘은 투 포인터다. 일단 공부는 한 알고리즘들처럼 개념 자체는 크게 어렵지 않았다. 항상 응용을 못하는 내가 문제일 뿐,,^^ 근데 이분탐색이랑 비슷한 거 같다고 느껴서 어떤 차이가 있는지는 좀 더 찾아봐야겠다.

---

문제

 

입출력 예시

 

아이디어 흐름

 

1) 필요한 변수 생성 및 초기화

◽ start, end = 0, 0

◽ total = 0

◽ cnt = 0

 

2) total과 주어진 M 값 비교

◽ total == M → cnt += 1, start += 1

◽ total < M → end += 1

◽ total > M → start += 1

◽ 모든 경우를 확인할 때까지 위의 과정을 반복

 

전체 코드

cnt = 0

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

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

total = 0

start, end = 0, 0

while start <= end and end <= len(a):
    total = sum(a[start:end])

    if total > m:
        start += 1
    elif total < m:
        end += 1
    else:
        cnt += 1
        start += 1

print(cnt)

 

코드를 처음 짰을 때는 total == M일 때 cnt 값만 1을 더해주고 포인터를 이동시키지 않았는데 입출력 예시대로 값이 안 나와서 start += 1을 추가해줬다. end += 1일 때는 어떻게 되나 싶어서 바꿔 제출해봤더니 채점 통과한 것을 보면 total 값에 따라 포인터가 움직일 거니까 totall == M인 경우에서는 어떤 포인터를 움직여도 상관이 없는 것 같다.

 

참고

투 포인터 개념 본다고 유튜브 영상 2개 찾아봤는데 두 영상 다 이 문제로 개념 설명을 했고 그 중에 나동빈 님의 코드를 참고용으로 가져와봤다.

# 영상에서는 n, m, data 값을 고정하셨는데 이 부분만 수정
n, m = map(int, input().split())
data = list(map(int, input().split()))

result = 0
summary = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한만큼 이동시키기
    while summary < m and end < n:
    	summary += data[end]
        end += 1
    # 부분 합이 m일 때 카운트 증가
    if summary == m:
    	result += 1
    
    summary -= data[start]

print(result)

 

start 변수를 따로 만들지 않고 for문을 이용한다는 것과 부분 합에서 data[start]를 빼는 방식이 인상 깊었다.