[Baekjoon] 20366. 一緒に雪だるまを作りますか?[G3]
6178 ワード
📚 質問する
https://www.acmicpc.net/problem/20366
📖 に答える
nは600で,4種類を組み合わせるとタイムアウトする.600 x 599 x 598 x 597=1000億を超える.
2つの組み合わせを選択します.残りの2つは、2つのポインタで差の最大値を探します.
このとき2つの組み合わせの数字に出会ったらスキップします.
📒 コード#コード#
def two_pointer(i, j): # 투포인터로 차이의 최소값을 찾아준다.
sum1 = arr[i] + arr[j] # 조합으로 고른 i, j의 합을 구한다.
s, e = 0, n - 1
min_abs = 10000000000
while s < e:
if s in [i, j]: # s, e가 i, j이면 건너뛴다.
s += 1
continue
elif e in [i, j]:
e -= 1
continue
min_abs = min(min_abs, abs(sum1 - (arr[e] + arr[s]))) # 최솟값 비교
if arr[e] + arr[s] >= sum1: # 크면 e를 움직인다.
e -= 1
else: # 작으면 s를 움직인다.
s += 1
return min_abs
n = int(input())
arr = sorted(list(map(int, input().split())))
min_result = 10000000000
for i in range(n):
for j in range(i + 1, n): # 조합으로 2개를 고른다.
min_result = min(min_result, two_pointer(i, j))
print(min_result)
🔍 結果
Reference
この問題について([Baekjoon] 20366. 一緒に雪だるまを作りますか?[G3]), 我々は、より多くの情報をここで見つけました https://velog.io/@yunhlim/Baekjoon-20366.-같이-눈사람-만들래-G3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol