오늘의 한 마디
투 포인터에 쫄지 말기!

• 백준 #2467 용액
• 백준 #1806 부분합
• 백준 #1644 소수의 연속합
• 현재 솔브닥 Class 5 문제를 풀고 있습니다.

백준 #2467 용액

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

예제 입력 1

5
-99 -2 -1 4 98

예제 출력 1

-99 98

예제 입력 2

4
-100 -2 -1 103

예제 출력 2

-2 -1

---

투 포인터

위 링크를 보면, 투 포인터가 어떤 느낌인지 알 수 있다.
뭔가 앞서거니 뒤서거니 하면서 찾아나가는 느낌을 받을 수 있다.

left와 right 변수를 사용하기 때문에 이분 탐색이랑 헷갈릴 수 있겠는데,
left 혹은 right를 반씩 줄여가면서 O(logn)에 특정 수를 찾는 이분 탐색과는 확실히 다르다!

투 포인터는 아래와 같은 문제에서 활용된다.

• 10개의 무작위 자연수가 주어졌을 때, 부분합이 5가 되는 경우가 총 몇 가지인지 구하라.
  • 누적합을 만들면 당연하게도 오름차순 정렬이 된다!
• 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾아라.
  • 가장 가까운 용액이라는 것은, 전체 경우를 다 보고 나서야 알 수 있는 것이다.
  • 따라서 부분합이 5가 되는 경우의 수를 세는 문제처럼, 용액의 합의 최솟값을 계속 갱신시켜나가면서 최종 최솟값일 때의 두 용액을 반환해야 한다.

다만, 위의 문제와 아래 문제의 차이점은 양수만 사용하는지, 음수도 사용하는지에 있다.
별로 큰 차이가 아니라고 느껴지겠지만...

left, right = 0, 0

(기본적으로 오름차순 정렬 상태다.)
모두 양수인 문제에서는 둘다 시작점에서 시작해야 부분합이 계속 앞서거니 뒤서거니 할 수 있다.
right를 끝에서 시작해버리면, 부분합이 최대에서 점점 줄어들기밖에 안하기 때문.

left, right = 0, N-1

하지만 음수도 있는 문제에서는 양 끝에서 시작해야 두 용액의 합이 0을 앞서거니 뒤서거니 할 수 있다.

투 포인터 문제를 풀 때는,

1. 이분 탐색과 헷갈리지 말 것.
2. left, right 초깃값에 대해 신중히 생각할 것.

풀이

# Yes! 단언컨대 투 포인터입니다. 

import sys
input = lambda: sys.stdin.readline().rstrip()
INF = int(2e9) # 처음에 1e9라고 했다가 런타임 에러 받았다. 

N = int(input())
l = list(map(int, input().split()))

left = 0
right = N-1

min_ = INF
min_left_idx = -1 # 이 변수를 따로 만들어주는 게 키포인트!
min_right_index = -1

while left < right:
    sum_ = l[left] + l[right]
    if abs(sum_) < min_:
        min_ = abs(sum_)
        min_left_idx = left
        min_right_idx = right
    
    if sum_ == 0:
        break

    if sum_ > 0:
        right -= 1
    else:
        left += 1

print(l[min_left_idx], l[min_right_idx])

---

백준 #1806 부분합

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

---

풀이

이게 바로 양수만 나오는 투 포인터다!

import sys
input = lambda: sys.stdin.readline().rstrip()
INF = 100001

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

# 누적합 만들기 -> sort됨
for i in range(1, N):
    arr[i] += arr[i-1]
arr.insert(0, 0)
    
# 0, 1에서 시작하는 투포인터
left = 0
right = 1
answer = INF
while True:
    s = arr[right] - arr[left]
    if s >= S:
        answer = min(answer, right-left)
        left += 1 # 차를 줄이는 효과
    else:
        if right != N:
            right += 1 # 차를 늘이는 효과
        else: # 끝
            break

print(answer if answer != INF else 0)

---

백준 #1644 소수의 연속합

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)
하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

예제 입력 1

20

예제 출력 1

0

예제 입력 2

3

예제 출력 2

1

예제 입력 3

41

예제 출력 3

3

예제 입력 4

53

예제 출력 4

2

---

풀이

소수의 누적합 리스트를 만들기 위해 에라토스테네스의 체를 만들어야 돼서 약간 복잡해지긴 했는데,
양수 투 포인터라는 근본은 변하지 않았다.

# 소수의 누적합?

import sys
input = lambda: sys.stdin.readline().rstrip()
import math

N = int(input())

# 에라토스테네스의 체 구현
eratos = [True] * (N+1)
eratos[0] = False
eratos[1] = False # 2-indexed
for i in range(2, int(math.sqrt(N))+1):
    if not eratos[i]:
        continue
    for j in range(i*2, N+1, i):
        eratos[j] = False

primes = [i for i in range(N+1) if eratos[i]]

# 누적합
for i in range(len(primes)):
    if i == 0:
        continue
    primes[i] += primes[i-1]
primes.insert(0, 0) # 소수 하나만으로 충족하는 경우도 재야 함. 

answer = 0
start, end = 0, 1
while start < len(primes) and end < len(primes):
    a = primes[end] - primes[start]
    if a == N:
        answer += 1
        
    if a < N:
        end += 1
    else:
        start += 1
    
print(answer)