1940
1940번: 주몽
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고
www.acmicpc.net
🐱🏍접근
입력받은 자연수 리스트를 오름차순으로 정렬한 후 양끝에서부터 포인터를 지정하여 두 수의 합을 구하는 방식으로 구현
시작 인덱스(s)는 리스트의 0번 인덱스에서부터 종료 인덱스(e)는 리스트의 마지막 (N-1)번 인덱스에서부터 시작
투 포인터 이동원칙
- lst[s] + lst[e] > M : e -= 1
- lst[s] + lst[e] < M : s += 1
- lst[s] + lst[e] == M : cnt +=1; s += 1; e-=1 //// 두 수의 합이 M이 될 경우 각 포인터를 한칸 씩 당겨주기
풀이
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
lst = list(map(int,input().split()))
lst.sort() # 리스트 정렬
# 사용 변수들 초기화
cnt = 0 # 합이 M인 경우의 수 카운트
s = 0 # 시작 인덱스 지정
e = N-1 # 마지막 인덱스 지정
while s < e :
if lst[s] + lst[e] == M :
print(f's:{s}({lst[s]}) e:{e}({lst[e]}) => 합이 {M}과 같음')
cnt += 1
s += 1
e -= 1
elif lst[s] + lst[e] < M :
print(f's:{s}({lst[s]}) e:{e}({lst[e]}) => 합이 {M} 보다 작음')
s += 1
else:
print(f's:{s}({lst[s]}) e:{e}({lst[e]}) => 합이 {M} 보다 큼')
e -=1
print(cnt)
## 입출력 예시
6
9
2 7 4 1 5 3
s:0(1) e:5(7) => 합이 9 보다 작음
s:1(2) e:5(7) => 합이 9과 같음
s:2(3) e:4(5) => 합이 9 보다 작음
s:3(4) e:4(5) => 합이 9과 같음
2
'🏷️CS > Algorithm' 카테고리의 다른 글
시간 복잡도 (0) | 2023.04.27 |
---|---|
[백준] 1253 (좋다) (1) | 2023.03.01 |
[백준] 2018(수들의 합5) (0) | 2023.02.25 |
[백준] 10986 (나머지 합) (0) | 2023.02.25 |
[백준] 11660(구간 합 구하기 5) (0) | 2023.02.25 |