우선 이 문제는 두 포인터를 활용한 문제다.
두 개의 눈사람 키 차이 중 최솟값을 구하는 문제이다.
문제 풀이를 보고 이해가 안 가는 부분이 있었는데,
a, b와 사이엔 최소 2개의 원소가 있어야 그 안에서 투포인터를 돌려 a, b로 이루어진 눈사람의 키와 차이가 가장 적은 눈사람을 만들 수 있다.
정렬된 배열에서 두 포인터를 돌리므로, a<=x<=....<==y<=b 순으로 되어있다.
내가 의문을 가진 부분은 a<=x<=y<=b 일 때였다.
(a, x)와 (y, b)로 이루어진 두 눈사람의 키 차이가 가장 적을 때 처음에 가정한 a,b로 이루어진 눈사람이 아니게 되어버리는 것이다.
이 문제에서의 중요한 점은 키 차이라는 것이다.
결국에 (a,x) , (y,b)로 눈사람을 만드는 경우, (a, b),(x,y)로 만들었을 때 같은 키 차이를 가진다.
다른 풀이를 봐도 내가 가진 의문 말고 a,b 사이에 두 개 이상의 눈덩이만 있어야 한다만 언급하고 내가 가진 의문을 해결하지 못해서 블로그에 써봤다.
import sys
N = int(input())
arr = sorted(list(map(int, input().split())))
ans = sys.maxsize
for i in range(N):
for j in range(i+3,N):
s, e = i+1, j-1
while s < e:
tmp = (arr[s] + arr[e])-(arr[i] + arr[j])
if abs(ans)>abs(tmp):
ans = abs(tmp)
elif tmp == 0:
ans = 0
print(0)
exit()
if tmp > 0:
e -= 1
else:
s += 1
print(ans)
'문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 15650번 문제풀이 (0) | 2021.08.03 |
---|---|
[C++] 백준 1149번 문제풀이 (0) | 2021.05.02 |
[C++] 백준 1167 번 문제풀이 (0) | 2021.04.06 |
[C++] 백준 2667번 문제풀이 (0) | 2021.03.20 |
[C++] 백준 2579번 문제풀이++] 백준 2579번 문제풀이 (0) | 2021.03.20 |