[BOJ] 1940. 주몽

Python3

문제

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

키워드

• 정렬
• 두 포인터

문제 풀이

문제 요구사항

N개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램

갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 m이 되면 갑옷이 만들어지게 된다.

변수 및 함수 설명

N : 재료의 개수 (1 ≤ N ≤ 15,000)
M : 갑옷을 만드는데 필요한 수 (1 ≤ M ≤ 10,000,000)
num : N개의 재료들이 가진 고유한 번호 (1 ≤ num ≤ 100,000)

ans : 갑옷을 만들 수 있는 개수
left : 왼쪽부터 시작하는 포인터
right : 오른쪽부터 시작하는 포인터

풀이

투 포인터 문제이다.

• num 배열을 입력받고 정렬해준다 (투 포인터의 필수적인 부분)
• 왼쪽 포인터가 가리키는 인덱스가 오른쪽 포인터가 가리키는 인덱스보다 작을 때까지 반복한다
• 만약 고유한 번호를 합친 값이 m보다 크면 오른쪽 포인터 값을 감소시킨다. (값을 더 작게 만들어야 하기 때문)
• 타겟 값(m)이면 ans를 1 증가시키고, left 값은 1 증가, right 값은 1 감소시킨다.
• 타겟 값보다 작으면 왼쪽 포인터를 증가시킨다. (합을 더 크게 만들기 위해)

최종 코드

n = int(input())
m = int(input())

num = list(map(int, input().split()))
num.sort()

ans = 0
left = 0
right = n - 1

while left < right:
    if num[left] + num[right] > m:
        right -= 1
    elif num[left] + num[right] == m:
        ans += 1
        left += 1
        right -= 1
    else:
        left += 1

print(ans)

피드백