[백준]230206 문제풀이

1654. 랜선 자르기

import sys

K, N = map(int, sys.stdin.readline().split())
cable = []
for i in range(K):
    cable.append(int(sys.stdin.readline()))

maxi = max(cable)
mini = 1
length = (maxi + mini)//2
ans_list = []
cables = 0

for i in cable:
    cables += i // maxi
if cables >= N:
    ans_list.append(maxi)

while abs(maxi - mini) > 1:
    cables = 0
    for i in cable:
        cables += i // length

    if cables > N:
        ans_list.append(length)
        mini = length
        length = round((maxi + length) / 2)
    elif cables == N:
        ans_list.append(length)
        mini = length
        length = round((maxi + length) / 2)
    else:
        maxi = length
        length = round((mini + length) / 2)
        continue

ans_list.append(mini)
print(max(ans_list))

조금은 엉성한 이분탐색으로 풀어냈다. 같은 변수를 가지고 계속 재할당하면서 풀어가다보니 변수가 헷갈릴 때가 많았다. 이분 탐색 개념을 가지고 문제에 맞게 최대한 간결하게 작성하는 법을 고민해봐야겠다.

2467. 용액

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
ans = []
idx1 = 0
idx2 = n-1

while idx2 - idx1 > 0:
    ans.append([abs(lst[idx1] + lst[idx2]), lst[idx1], lst[idx2]])
    diff = abs(lst[idx1] + lst[idx2])
    if abs(lst[idx1+1] + lst[idx2]) <= diff:
        idx1 += 1
    elif abs(lst[idx1] + lst[idx2-1]) <= diff:
        idx2 -= 1
    else:
        ans.append([abs(lst[idx1] + lst[idx2]), lst[idx1], lst[idx2]])
        idx1 += 1
        idx2 -= 1

ans.sort()

print(ans[0][1], ans[0][2])

처음으로 완전히 혼자 푼 골드 문제! 너무 뿌듯하다. 근데 풀고보니 문제 카테고리가 이분 탐색이랑 두 포인터인데 이상한 방식으로 풀어서 아직 문제를 푸는 방법에 대해 잘 파악하기는 쉽지 않은 것 같다. 양쪽 끝의 인덱스를 하나씩 줄이면서 비교해서 더 낮은 절대값이 나오는 인덱스로 초기화하고, local minimum을 찾으면 양쪽 인덱스를 모두 좁혀서 다시 처음부터 똑같은 과정을 반복하도록 했다.