Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 힙
- N과M
- programmers
- 가상메모리 관리
- 딕셔너리
- 운영체제
- 코딩테스트
- 재귀
- 프로그래머스
- 그리디
- dict
- 다익스트라
- 스택
- MYSQL
- 구현
- level0
- python
- 가상메모리
- 다이나믹 프로그래밍
- 백준
- level2
- 파이썬
- level3
- 수학
- dfs
- 브루트포스
- level1
- BFS
- BOJ
- DP
Archives
- Today
- Total
동캄의 코딩도장
백준 1654 [랜선 자르기] 파이썬 본문
https://www.acmicpc.net/problem/1654
처음 접근은 평균을 내고, 평균부터 시작해서 1씩 빼면서 N개를 만들 수 있는지 탐색하였다. 시간 초과가 발생하였다.
#백준 1654 랜선 자르기 시간초과 코드
K,N=map(int,input().split())
lans=[]
lans_sum=0
lans_avg=0
temp=0
for _ in range(K):
lan=int(input())
lans_sum+=lan
lans.append(lan)
lans_avg=lans_sum//N
temp=lans_avg
while temp>0:
cnt=0
for lan in lans:
cnt+=lan//temp
if cnt>=N:
answer=temp
break
temp-=1
print(answer)
어떻게 풀지를 생각하다가 이분 탐색을 사용하면, 탐색 수가 줄겠구나 라는 생각이 들어 이분 탐색으로 도전하였다.
#백준 1654 랜선 자르기
K,N=map(int,input().split())
lans=[]
lans_sum=0 # 랜선의 총합
lans_end=0 # 탐색 끝 범위
lans_start=0 #탐색 시작 점위
temp=0 # 탐색 기준점 (중점)
answer=0 # 정답
for _ in range(K): #우선 리스트에 저장
lan=int(input())
lans_sum+=lan
lans.append(lan)
lans_end=(lans_sum//N)+1 #끝점을 초기화
while True:
cnt=0
if lans_start==lans_end:
break
temp=(lans_end+lans_start)//2 #중점을 설정
for lan in lans:
cnt+=lan//temp
if cnt>=N: # 개수가 N게 이상이면, 정답을 temp로 설정
answer=temp
lans_start=temp+1 # lans_start(temp+1)~lans_end의 범위를 탐색
break
if cnt<N: # 개수가 N개 이하이면
lans_end=(temp) # # lans_start~lans_end(temp)의 범위를 탐색
print(answer)
K개의 단순합을 N으로 나눈 평균을 lans_end라고 했다.
초기 탐색 범위는 [0, lans_sum//N+1] 이고,
개수를 N개 이상 만들 수 있으면, 탐색 범위는 [temp+1,lans_end]
개수를 N개 미만으로 만들 수 있으면, 탐색 범위는 [lans_start,temp] 이다.
이분 탐색을 계속 하다, lans_start==lans_end 이면 탐색을 종료한다.
'코테 > BOJ' 카테고리의 다른 글
백준 11723 [집합] 파이썬 (0) | 2023.03.20 |
---|---|
백준 18111 [마인크래프트] 파이썬 (0) | 2023.03.20 |
백준 6588 [골드바흐의 추측] 파이썬 (0) | 2022.10.11 |
백준 17427 [약수의 합 2] 파이썬 (0) | 2022.10.09 |
백준 4375 [1] 파이썬 (0) | 2022.10.09 |