[백준 파이썬] 2467 용액

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

1520번: 내리막 길

문제



주어진 2차원 배열에서 내리막으로만 갈 수 있는 길의 경우의 수를 계산하는 문제이다.

---

풀이

용액을 비교해가며 풀어야하는 문제이므로 이분탐색을 이용하였다.

 

먼저 가장 왼쪽값을 0부터 N-1 까지 순회하며 바꿔주는데 이 과정에서 이분탐색을 적용해줬다.

if abs(tmp) < ans:
        lAns = i
        rAns = mid
        ans = abs(tmp)

왼쪽값과 중앙값을 더한 값의 절대값이 현재 정답값보다 작다면 정답값을 교체해준다.

 

if tmp == 0:
    break
elif tmp < 0:
    low = mid + 1

else:
    high = mid - 1

이후 더한값이 0이라면 최소값이므로 반복문을 탈출한다.

0보다 작을 경우 왼쪽값이 더 크다는 것을 의미하므로 low를 mid + 1값으로 바꾼다.

0보다 클 경우 오른쪽값이 크므로 high를 mid - 1 값으로 변경한다.

 

print(liquid[lAns], liquid[rAns])

최종적으로 왼쪽값과 오른쪽값을 출력한다.

 

코드

N = int(input())
liquid = list(map(int, input().split()))

ans = float("INF")
lAns = 0
rAns = N - 1

for i in range(N - 1):
    low = i + 1
    high = N - 1
    
    while low <= high:
        mid = (low + high) // 2
        tmp = liquid[mid] + liquid[i]
        
        if abs(tmp) < ans:
            lAns = i
            rAns = mid
            ans = abs(tmp)
        
        if tmp == 0:
            break
        elif tmp < 0:
            low = mid + 1
            
        else:
            high = mid - 1

print(liquid[lAns], liquid[rAns])