[Python] 백준 1940번 - '주몽' 풀이

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

1940번: 주몽

 

---

코드

import sys
def binary_search(list, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if target == list[mid]:
            return 1
        elif target > list[mid]:
            start = mid + 1
        else:
            end = mid - 1
    return 0
N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
n_list = list(map(int, sys.stdin.readline().rstrip().split()))
cnt = 0
n_list.sort()
for i in n_list:
    m = M - i
    cnt += binary_search(n_list, m, 0, N-1)
print(cnt//2)

이 문제를 보자마자 어제 배운 이진탐색을 이용하고 싶었습니다.

https://cuckoobird.tistory.com/17

[Python] 백준 1920번 - '수 찾기' 풀이 + 이진탐색 (이분탐색)

이진탐색 문제를 풀이한 해당 글입니다.

 

그래서 제가 구성한 풀이방법은

 

1. 배열을 정렬하자

2. m 이라는 변수에 M - 배열[i] 를 저장하여 두가지 재료중 나머지 하나를 알아내자

3. 변수 m 을 알아내는 방법은 이진탐색을 이용하여 리턴값을 cnt에 저장하자 -> cnt는 결과의 두배일테니 //2를 하자

 

였습니다. 생각을 쓰고 코드로 적으니 정답이 나오네요.

---

후기

좀 더 복잡한 문제를 풀었어야 했나 생각이 들기도 하지만 배운 것을 생각한 것 만해도 잘 했다는 생각이 들고 뿌듯하네요. ㅎㅎ 생각이 정답으로 도출되어 기쁘고 즐겁습니다.