[Python] 백준/BOJ 15810번: 풍선 공장 (Silver 2)

2025. 2. 23. 11:00·Algorithm/백준 (BOJ)
반응형

💻 Problem

문제 보러 가기

 

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.

풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.

대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!

각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.

모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.

 

💡 Approach

완전 탐색으로 풀면 최악의 경우는 N, M, Aj가 최대인 10^6일 때이다.

풍선을 만드는 데에 10^6이 걸리는 10^6명의 스태프가 10^6개의 풍선을 만들어 보자.

10^6분 일 때 각자 하나씩 만들어서 10^6개의 풍선이 된다.

즉 시간복잡도는 10^6 * 10^6 = 10^12이므로 1초를 초과한다.

 

그러니 이분탐색으로 풀면 된당.

 

✏️ Solution

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 스태프의 수, 풍선의 개수
time = list(map(int, input().split())) # 각 스태프가 풍선 하나를 만드는데 걸리는 시간
time.sort()

start, end = 0, time[-1] * m
ans = end

while start <= end:
    mid = (start + end) // 2 # 풍선이 다 만들어지는 시간
    cnt = 0 # 풍선 개수

    # 현재 mid 기준 풍선이 만들어지는 개수
    for t in time:
        cnt += mid // t

    # 풍선을 충분히 만들었다면 더 짧은 시간으로 탐색
    if cnt >= m:
        ans = mid
        end = mid - 1

    # 풍선을 다 못만들었다면 더 긴 시간으로 탐색
    else:
        start = mid + 1

print(ans)

이분탐색의 시간복잡도는 O(log n)이다.

최대 시간을 t라고 했을 때 전체 시간복잡도는 O(log n * t)이다.

  • log 10^6 * 10^6 = log 2^20 * 10^6 = 2 * 10^ 7

 

import sys
input = sys.stdin.readline

n, m = map(int, input().split()) # 스태프의 수, 풍선의 개수
time = list(map(int, input().split())) # 각 스태프가 풍선 하나를 만드는데 걸리는 시간
time.sort()

start, end = 0, time[-1] * m

while start + 1 < end:
    mid = (start + end) // 2 # 풍선이 다 만들어지는 시간
    cnt = 0 # 풍선 개수

    # 현재 mid 기준 풍선이 만들어지는 개수
    for t in time:
        cnt += mid // t

    # 풍선을 충분히 만들었다면 더 짧은 시간으로 탐색
    if cnt >= m:
        end = mid

    # 풍선을 다 못만들었다면 더 긴 시간으로 탐색
    else:
        start = mid

print(end)

반열린구간 이분탐색으로 풀어봤다.

start를 열어줬기 때문에 답은 end가 된다.

반응형

'Algorithm > 백준 (BOJ)' 카테고리의 다른 글

[Python] 백준/BOJ 30804번: 과일 탕후루 (Silver 2)  (0) 2025.02.25
[Python] 백준/BOJ 10425번: 피보나치 인버스 (Silver 2)  (2) 2025.02.24
[Python] 백준/BOJ 7662번: 이중 우선순위 큐 (Gold 4)  (0) 2025.02.22
[Python] 백준/BOJ 17626번: Four Squares (Silver 3)  (0) 2025.02.21
'Algorithm/백준 (BOJ)' 카테고리의 다른 글
  • [Python] 백준/BOJ 30804번: 과일 탕후루 (Silver 2)
  • [Python] 백준/BOJ 10425번: 피보나치 인버스 (Silver 2)
  • [Python] 백준/BOJ 7662번: 이중 우선순위 큐 (Gold 4)
  • [Python] 백준/BOJ 17626번: Four Squares (Silver 3)
올콩
올콩
콩 심은 데 콩 난다
  • 올콩
    콩스토리
    올콩
  • 전체
    오늘
    어제
    • 분류 전체보기 (196) N
      • SSAFY (10)
      • Algorithm (114) N
        • 이론 (6)
        • 백준 (BOJ) (107) N
        • 프로그래머스 (1)
      • Trouble Shooting (9)
      • Frontend (6)
      • React (17)
      • Next.js (4)
      • Vue (4)
      • Node.js (2)
      • HTML (9)
      • DevOps (4)
        • Git (4)
      • Language (9)
        • JavaScript (0)
        • Java (9)
      • Embedded (1)
      • CS (5)
        • Network (1)
        • Blockchain (4)
      • 자격증 (2)
  • 블로그 메뉴

    • GitHub
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    우선순위큐
    React
    html5
    Next.js
    Algorithm
    재귀
    SSAFY
    중복순열
    브루트포스
    Heap
    백트래킹
    DP
    블록체인
    백준
    수학
    티스토리챌린지
    싸피
    중복조합
    bfs
    Java
    알고리즘
    강의
    구현
    순열
    SSAFYcial
    오블완
    파이썬
    dfs
    Error
    힙
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
올콩
[Python] 백준/BOJ 15810번: 풍선 공장 (Silver 2)
상단으로

티스토리툴바