[백준 1940] 주몽의명령 feat 투포인터
By Freedom••2분 읽기

[백준 1940] 주몽의명령 feat 투포인터

알고리즘
Status
Published
Category
알고리즘
Tags
Python
알고리즘
Author
Published Date
Jul 17, 2025
Featured Image
https://i.postimg.cc/1XSMzTft/image.png
주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.
갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.
 
notion image

냅다 풀기

재료개수, 압옷을 만드는데 필요한 수, 재료들의 번호를 입력받고 count 선언을 해놓고… 모든 재료를 두 개 씩 짝지어보면 되지 않나? 짝 지을때마다 count++ 하는 방식으로!
# 입력 받기
N = int(input())  # 재료 개수
M = int(input())  # 갑옷을 만드는데 필요한 수
materials = list(map(int, input().split()))  # 재료들의 번호

# 냅다 풀기 - 완전 탐색
count = 0

# 모든 재료를 두 개씩 짝지어보기
for i in range(N):
    for j in range(i+1, N):
        if materials[i] + materials[j] == M:
            count += 1

print(count)
이중 for문? → 시간복잡도 O(N²) 제한시간이 2초면 1초당 1억번안에 끝내야하니까…. 2억번?
왜 1억번인가? (옛날 포스트 참고!)
최악의 경우를 생각했을때
재료의 개수 N(1 ≤ N ≤ 15,000)
필요한 수 M(1 ≤ M ≤ 10,000,000)
… 딱봐도 터질것같다.

필요한 개념

  • 정렬
    • 정렬 알고리즘이 아주 다양하다. 버블, 선택, 삽입 등등등.. 추후에 다루자
    • 해당 문제에서는 단순 파이썬 내장 정렬 함수인 sort()를 사용
    • 시간복잡도는 O(N log N)
 

문제 적용하기

두 재료의 번호를 더해서 M이 되는 경우를 찾는다.
저번 포스트에서 연속된 자연수의 합으로 표현하는 방법의 수를 구할때 투 포인터 개념을 사용했다.
이번 문제에서도 비슷한 맥락이긴 하나 연속된 숫자가 아니라, 아무 두 숫자의 합이 M이 되는 경우를 찾는 것이 핵심이다.
냅다 문제 풀기 처럼 단순히 모든 경우의 수를 다 해보면 → O(N²)
정렬 후 투 포인터를 쓰면 O(N) 으로 해결 가능하다.
 
투 포인터의 조건을 아래와 같이 설정하자.
조건
행동
재료[start] + 재료[end] == M
갑옷 1개 제작 → count += 1 → 두 포인터 모두 이동
재료[start] + 재료[end] < M
합이 부족 → start를 오른쪽으로 이동
재료[start] + 재료[end] > M
합이 초과 → end를 왼쪽으로 이동
// 1. 배열을 정렬한다 → 투포인터를 위해 필요
// 2. start, end 포인터를 배열 양 끝에 둔다
// 3. 두 수의 합을 계산하면서 포인터를 이동한다
//    - 합이 목표보다 작으면 start를 오른쪽으로
//    - 합이 목표보다 크면 end를 왼쪽으로
//    - 딱 맞으면 count 증가 후 두 포인터 모두 이동
// 4. start가 end를 넘으면 종료
입력: N (재료의 개수), M (목표 합)
입력: 재료 리스트 A[1..N]

1. 재료 리스트 A를 오름차순으로 정렬한다.

2. start = 0
   end = N-1
   count = 0   // 갑옷 개수

3. while (start < end):
      sum = A[start] + A[end]

      if sum == M:
          count += 1    // 갑옷 완성!
          start += 1    // 왼쪽 포인터 이동
          end -= 1      // 오른쪽 포인터 이동

      else if sum < M:
          start += 1    // 더 큰 값을 찾아야 함

      else if sum > M:
          end -= 1      // 더 작은 값을 찾아야 함

4. count를 출력한다.
import sys

input = sys.stdin.readline

# 입력 받기
N = int(input())           # 재료 개수
M = int(input())           # 목표 합
A = list(map(int, input().split()))   # 재료 번호 리스트

# 재료 리스트 정렬
A.sort()

# 투 포인터 초기화
start = 0
end = N - 1
count = 0    # 갑옷 개수

# 투 포인터 탐색
while start < end:
    sum = A[start] + A[end]

    if sum == M:
        count += 1
        start += 1
        end -= 1

    elif sum < M:
        start += 1

    else:  # sum > M
        end -= 1

# 결과 출력
print(count)