1940

날짜 : 2023. 05. 28

사용 언어 : python

 

문제

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

 

 

코드

import sys
n = int(sys.stdin.readline())  # 재료의 개수
m = int(sys.stdin.readline())  # 갑옷 제작 필요 개수
a = list(map(int, sys.stdin.readline().split()))
a.sort(reverse=True)  # 내림차순 정렬
res = 0
s, e = 0, n-1
while s < e:
    if a[s] >= m:  # 1개만으로 m값 넘김
        s += 1  # 줄이기
        continue
    if a[s] + a[e] == m:  # 제작 가능
        res += 1
        s += 1
        e -= 1
        continue
    elif a[s] + a[e] > m:  # 합쳐서 넘기는 경우
        s += 1
    else:
        e -= 1
print(res)

 

 

풀이

- n, m값과 각 갑옷의 value를 입력받은 다음 값옷을 내림차순으로 정렬한다.

- 그 다음 해당 갑옷들의 시작과 끝을 설정할 인덱스 s, e를 생성 후 이진탐색 방식으로 탐색한다.

- 1개 자체의 값의 m보다 큰 경우에는 다음 케이스로 넘어가고,

- 합했을 때 m과 동일한 경우 s는 +1, e는 -1을 실행한다.(각각의 갑옷의 값은 줄어들고, 늘어난다.)

- 제작 불가능한 경우(값이 못미치는 경우)에는 e값을 줄여서 합을 늘리고, 반대의 경우에는 s값을 늘려서 값을 줄여나간다.

 

 

알게된 점

- 

 

 

참고 사이트

-