[BOJ] 1806번: Subsequence (부분합)

자신감 MAX로 골드 문제에 도전했다가 실버 문제로 경험치 더 쌓자는 생각을 하게 되었다 ❗ 여러 블로그를 참고했기 때문에 나중에 다른 언어로 다시 풀어봐야겠다.

---

문제

부분합을 구하는 걸 봤을 때 전형적인 투 포인터 유형이다.

 

 

입출력 예시

다른 투포인터 유형 문제들처럼 입출력 예시가 매우 간단함

 

 

아이디어 흐름

 

1) start, end, total(S와 비교할 부분합 저장 변수) 초기화

 

2) start, end 이동 방향 생각

◽ 둘다 인덱스가 커지는 방향

◽ start는 인덱스가 커지는 방향, end는 인덱스가 작아지는 방향

→ 부분 수열의 최소 길이를 구하는 것이 목표이기 때문에 둘다 인덱스가 증가하는 방향으로 값을 바꾸는 게 좋을 것 같다.

 

3) start, end 값 변화 조건 설정 및 수열 길이 확인

◽ total >= S → 일단 정답 후보가 되기 때문에 확인 후 다음 숫자로 넘어가기 위해 start += 1

◽ 현재 answer 값과 위의 조건을 만족하는 부분 합 수열을 만났을 때 수열 길이를 비교하고 더 작은 값으로 answer 갱신

◽ total < S → total 값에 arr[end] 값을 더해주고 end += 1

 

4) 확인이 끝나는 조건 설정

◽ end == N일 경우 끝까지 다 확인한 것이기 때문에 while문을 빠져나온다.

 

 

전체 코드

# Gold 4

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

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

start, end = 0, 0

total = 0

# 임의의 큰 값으로 지정
answer = 100001

while True:
    if total >= s:
        total -= arr[start]
        answer = min(answer, end-start)
        start += 1
    else:
        if end == n:
            break
        else:
            total += arr[end]
            end += 1

# 초기값이 그대로라면 답을 찾지 못한 경우이기 때문에 0 출력
if answer == 100001:
    print(0)
else:
    print(answer)

 

투 포인터 유형 문제에서 인덱스 값이 start일 때까지의 값을 빼는 코드가 종종 보이는데 사실 저 의미를 정확하게 이해하지 못했다. 계속 더해나가는 방식이 편해서 그렇게 쓰고 있긴 한데 너무 한 가지 방법만 쓰면 사고 방식이 거기 갇힐까봐 이해하려고 노력 중이다. 투 포인터 유형 이번엔 봐줬지만 다음은 그냥 보내지 않겠다 🤜