유형 : 투포인터 알고리즘
올림피아드 초등부 1번문제
문제풀이
이미 정렬된 배열이 들어온다는 것을 이용한다.
1. 두 포인터 l과 r에 맨 첫 요소와 마지막 요소의 주소를 넣는다.
2-1. l과 r의 합이 양수일 경우에는 r이 더 작아져야하므로 r을 하나 앞으로 옮겨준다.
2-2. l과 r의 합이 음수을 경우에는 l이 더 커져야하므로 l을 하나 뒤로 옮겨준다.
3. 이때, l과 r의 합의 절댓값이 이전에 기억해둔 l과 r의 합의 절댓값보다 작다면 이 값과 l, r값을 기억해둔다.
예시
1. l과 r의 합이 5 이므로 r을 하나 앞으로 당겨준다. 이 때 5와 (-10, 15)를 기억해둔다.
2. l과 r의 합이 -6 이므로 l을 하나 뒤로 옮겨준다. 이때의 합의 절댓값 6은 5보다 크므로 기억해둘 필요는 없다. 이런식으로 진행하다보면 4에서 저장된 -5와 4의 합의 절댓값이 끝까지 살아남게 된다.
5과정 이후에는 l+r이 항상 양수이므로 r이 계속 낮아지다가 l보다 낮아지면 알고리즘이 종료된다.
Python code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import sys
def solution(liq):
l=0
r=len(liq)-1
ans = [abs(liq[l]+liq[r]),(liq[l],liq[r])]
while l<r:
mix = liq[l]+liq[r]
if abs(mix) < ans[0]:
ans[0] = abs(mix)
ans[1] = (liq[l],liq[r])
if mix > 0:
r-=1
elif mix < 0:
l += 1
else:
return ans[1]
return ans[1]
if __name__== "__main__":
n = map(int,sys.stdin.readline().split())
liq = list(map(int,sys.stdin.readline().split()))
ans = solution(liq)
print("{} {}".format(ans[0],ans[1]))
|
cs |
후기
리스트만 입력값으로 들어오는줄 알고 21 line을 빼먹었다가 한참을 헤맸다...
파이썬으로 푼 사람이 많지는 않지만 1등을 해보는 날이 오다니..
문제 링크
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
www.acmicpc.net
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 2469 사다리 타기 (0) | 2020.03.19 |
|---|---|
| 백준 2468 안전 영역 (0) | 2020.03.17 |
| 백준 1300 K번째 수 (0) | 2020.03.11 |
| 백준 17214 다항 함수의 적분 (0) | 2020.03.10 |
| 백준 2869 달팽이는 올라가고 싶다 (0) | 2020.03.09 |