[백준] 1940 파이썬(python) : 주몽

1940번 : 주몽

 

 

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
number = list(map(int, sys.stdin.readline().split()))
number.sort() #1
cnt, tmp = 0, 0
start, end = 0, n-1 #2
while start < end: #3
    tmp = number[start] + number[end] #4
    if tmp < m: #5
        start += 1
    elif tmp > m: #6
        end -= 1
    else: #7
        cnt += 1
        start += 1
        end -= 1
print(cnt)

 

#1 : 재료들을 고유한 번호에 따라 정렬

#2 : 두 개의 포인터가 각각 끝을 가리키도록 지정

#3 : start포인터가 end포인터보다 작을떄만 반복

#4 : 두 재료 고유번호의 합

#5 : tmp가 m보다 작을때, start포인터를 1증가

#6 : tmp가 m보다 클때, end포인터를 1감소

#7 : tmp가 m과 같을때, cnt 1증가 start포인터 1증가, end포인터 1감소(원하는 값을 찾았으니 땡겨준다 생각)

 

투 포인터 문제인데 부분집합의 누적합을 구하는 문제가 아닌 두 재료 중 고유번호의 합이 m이 되는 재료의 쌍을 찾는 문제다. (갑옷은 두 개의 재료로 만든다고 문제에 명시되어 있음)

 

---

2018번 : 두 수의 합 5