문제 접근 🤔
- 책을 먼저 보고 후에 봐서 방향성과 코드는 알았다.
- 총 떡의 길이를 자른 값이 n보다 크면
- 더 큰 수로 빼야해서 오른쪽 (큰쪽으로 이동)
- 총 떡의 길이를 자른 값이 n보다 작으면
- 더 작은 수로 빼야해서 왼쪽 (작은쪽으로 이동)
놓쳤던 부분 😅
- 이진 탐색은 응용이 어렵다. 안보고 했으면 불가능했었다.
코드 😁
첫 번째 코드
# 201 Page
n, m = map(int, input().split())
k = list(map(int, input().split()))
start = 1
end = max(k) # 떡 중의 최대 길이
while start <= end:
mid = (start + end) // 2
total = 0
for i in k:
if i < mid:
continue
total += i - mid
if total == m:
print(mid)
if total > m:
start = mid + 1
else:
end = mid - 1
문제 접근 🤔
- 문제 이해가 안가서 계속 보다가 결국 해답을 봤다.
놓쳤던 부분 😅
- 문제에서 120, 110, 140, 150에서 140, 150만 상한액으로 만들라는거에 꼽혀서 이것만 생각하다가 결국 최댓값만 찾으면 되는거였다.
코드 😁
첫 번째 코드 - 티스토리 블로그
# 출처 : <https://great-park.tistory.com/44>
import sys
N = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))
K.sort()
M = int(sys.stdin.readline())
start = 1
end = max(K)
while start <= end:
mid = (start + end) // 2
amount = 0
for x in K:
if x <= mid:
amount += x
else:
amount += mid
if amount > M:
end = mid - 1
else:
start = mid + 1
print(end)
문제 접근 🤔
- 떡볶이 문제랑 동일하게 코드를 작성했는데 백준에서는 오류가 떴다.
놓쳤던 부분 😅
- break문을 사용하면 절대 안된다.
- 최대값을 찾는거여서 끝까지 탐색하게 해야했다.
- 특정 조건일때 왼쪽, 오른쪽으로 보낼지 아직도 헷갈린다.
코드 😁
첫 번째 코드 - 백준 질문 게시판
# 떡볶이 문제랑 일치
import sys
tree_count, tree_length = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
start = 0
end = max(tree)
while start <= end:
mid = (start + end) // 2
total = 0
for cut in tree:
if cut > mid:
total += cut - mid
if total >= tree_length:
start = mid + 1
else:
end = mid - 1
print(start-1)
문제 접근 🤔
- 이진 탐색을 책으로 읽고 확인 후 문제를 파악 했다.
- 랜선의 최대값을 받고 이진 탐색으로 좁혀가면 될 것 같았다.
놓쳤던 부분 😅
- 두 번째 코드
- 제일 최댓값을 찾아야하는데 값을 찾고 break을 걸어서 사실상 이진 탐색이 아니게 됐다. break를 지우고 result에 최대값을 계속 넣는 식으로 결과를 나오게 하니깐 되긴했는데 ZeroDivisionError가 발생했다.
- 세 번째 코드
- 시작 위치를 0으로 잡아서 mid가 0으로 되어서 생긴 에러 였다.
코드 😁
첫 번째 코드 - 실패
import sys
# 4개의 랜선이 있고 11개를 만들어야한다.
K, N = map(int, sys.stdin.readline().split())
lan_list = list(int(sys.stdin.readline()) for _ in range(K))
start = 0
end = max(lan_list)
while start <= end:
total = 0
mid = (start + end) // 2
for i in lan_list:
total += i // mid
if total == N:
print(mid)
break
# 랜선이 많으면
if total > N:
start = mid + 1
# 랜선이 적으면
else:
end = mid - 1
두 번째 코드 - 실패 (ZeroDivisionError)
import sys
# 4개의 랜선이 있고 11개를 만들어야한다.
K, N = map(int, sys.stdin.readline().split())
lan_list = list(int(sys.stdin.readline()) for _ in range(K))
start = 0
end = max(lan_list)
result = 0
while start <= end:
total = 0
mid = (start + end) // 2
for i in lan_list:
total += i // mid
# 랜선이 많으면
if total >= N:
result = mid
start = mid + 1
# 랜선이 적으면
else:
end = mid - 1
print(result)
세 번째 코드
import sys
# 4개의 랜선이 있고 11개를 만들어야한다.
K, N = map(int, sys.stdin.readline().split())
lan_list = list(int(sys.stdin.readline()) for _ in range(K))
start = 1
end = max(lan_list)
result = 0
while start <= end:
total = 0
mid = (start + end) // 2
for i in lan_list:
total += i // mid
# 랜선이 많으면
if total >= N:
result = mid
start = mid + 1
# 랜선이 적으면
else:
end = mid - 1
print(result)
'항해99' 카테고리의 다른 글
항해99 알고리즘 16회차 (0) | 2023.12.30 |
---|---|
항해99 알고리즘 15회차 (0) | 2023.12.29 |
항해99 알고리즘 13회차 (1) | 2023.12.26 |
항해99 알고리즘 12회차 (0) | 2023.12.26 |
항해99 알고리즘 11회차 (0) | 2023.12.25 |