다이나믹 프로그래밍
2. 문제풀이
2-1 2110. 공유기 설치
X.sort()를 해준다
임의의 거리를 두면서 공유기를 설치, 공유기의 총 개수(count)를 센다.
count >= C --> 이때의 임의의 거리가 공유기 사이의 최대 거리가 된다X.sort()
start = 1
end = X[-1] - X[0]
result = 0
while start <= end:
mid = (start + end)//2 #공유기 사이의 거리
count = 1 #설치한 개수
ip = X[0]
for i in range(1, N):
if X[i] >= X[0]+mid:
ip = X[i]
count += 1
if count >= C:
start = mid+1
result = mid
else:
end = mid-1
print(result)2-2 1300. K번째 수
N = 20, B[k] = 20 일때
k값은 20보다 같거나 작은 원소들의 합
행 1: 1*1 .... 1*20
2: 2*1 .. 2*10
3: 3*1 .. 3*6
4: 4*1 .. 4*4
...
9: 9*1 9*2
10: 10*1 10*2
11: 11*1
...
18: 18*1
19: 19*1
20: 20*1
이때 B[k]//행 = 그 행에서 B[k]보다 같거나 작은 숫자의 개수(최대 N개)
start = 1
end = N*N
result = 0
while start <= end:
preindex = 0
mid = (start + end)//2 # 임의의 B[n]의 값
for i in range(1, N+1):
preindex += min(mid//i, N)
if preindex >= k: # k값이 작을때 = 임의의 B[n]이 B[k]보다 클때
end = mid-1
result = mid
else: # k값이 클때 = 임의의 B[n]이 B[k]보다 작을때
start = mid+1
print(result)2-3 12015. 가장 긴 증가하는 부분 수열2
N번은 무조건 돌아야 함(하나씩 비교)
1. list를 하나 만들어서 들어오는 값과 비교하여
2. 가장 큰 값보다 크면 append,
3. 작으면 list[i] < X <= list[i+1]위치 찾기 ==> 이분탐색
4. list[i+1]위치에 값 삽입
2-4 2805. 나무 자르기
나무의 수 = N, 나무의 길이 = M, 나무들 = trees
M을 판별의 기준으로 한다
start = 0
end = sum(trees)
mid = (start+end)//2 ==> 잘라야 하는 임의의 위치
result = 0
while start <= end:
mid = (start + end) // 2
s = 0
for i in tree:
if i > mid:
s += i - mid
if s >= M:
start = mid + 1
result = mid
else:
end = mid - 1