[백준(BOJ)] 16401 과자 나눠주기 - 스위프트 (Swift)

2024. 1. 21. 20:28· PS/BOJ
목차
  1. [Silver II] 과자 나눠주기 - 16401
  2. 성능 요약
  3. 분류
  4. 제출 일자
  5. 문제 설명
  6. 입력
  7. 출력
  8. 풀이

[Silver II] 과자 나눠주기 - 16401

문제 링크

성능 요약

메모리: 144000 KB, 시간: 740 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2024년 1월 19일 14:22:10

문제 설명

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

 

풀이

우선 막대과자의 길이를 이분 탐색을 통해 구해주면 되는 문제입니다.

막대과자의 길이를 기준으로 몇 명의 조카들에게 줄 수 있는 지를 구합니다.

 

만약 구해진 명수가 적다면 막대과자의 길이를 줄여 더욱 더 많은 조카에게 줄 수 있도록 하고,
명수가 많거나 같다면 막대과자의 길이를 늘려 더욱 더 적은 조카에게 주지만, 최대의 길이를 줄 수 있도록 하면 됩니다.

 

다음은 코드입니다.

let mn = readLine()!.split(separator: " ").map { Int($0)! }
let (m, n) = (mn[0], mn[1])
var nephews = readLine()!.split(separator: " ").map { Int($0)! }
nephews.sort()
var (left, right, ans) = (1, nephews.reduce(0, { max($0, $1) }), 0)

while left <= right {
    let mid = (left + right) / 2
    var count = 0
    for nephew in nephews {
        count += nephew / mid
    }

    if count >= m {
        ans = mid
        left = mid + 1
    } else {
        right = mid - 1
    }

}

print(ans)
728x90

'PS > BOJ' 카테고리의 다른 글

[백준(BOJ)] 9024 두 수의 합 - 스위프트 (Swift)  (2) 2024.01.21
[백준(BOJ)] 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야 - 스위프트 (Swift)  (2) 2024.01.21
[백준(BOJ)] 13397 구간 나누기 2 - 스위프트 (Swift)  (0) 2024.01.18
[백준(BOJ)] 2343 기타 레슨 - 스위프트 (Swift)  (0) 2024.01.18
[백준(BOJ)] 1654 랜선 자르기 - 스위프트 (Swift)  (0) 2024.01.18
  1. [Silver II] 과자 나눠주기 - 16401
  2. 성능 요약
  3. 분류
  4. 제출 일자
  5. 문제 설명
  6. 입력
  7. 출력
  8. 풀이
'PS/BOJ' 카테고리의 다른 글
  • [백준(BOJ)] 9024 두 수의 합 - 스위프트 (Swift)
  • [백준(BOJ)] 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야 - 스위프트 (Swift)
  • [백준(BOJ)] 13397 구간 나누기 2 - 스위프트 (Swift)
  • [백준(BOJ)] 2343 기타 레슨 - 스위프트 (Swift)
Dev_Ted
Dev_Ted
250x250
Dev_Ted
프로그래밍 성장기
Dev_Ted
전체
오늘
어제
  • 분류 전체보기 (123) N
    • CS (10)
      • 자료구조 (Data Structure) (1)
      • 알고리즘 (Algorithm) (5)
      • 데이터베이스 (Database) (0)
      • 네트워크 (Network) (0)
      • 컴퓨터 구조 (Computer Architecture) (0)
      • 운영체제 (Operating System) (0)
      • 프로그래밍 언어 (Programming Language) (2)
    • PS (78)
      • BOJ (78)
      • LeetCode (0)
    • Swift (6)
      • 문법 (0)
    • iOS (21) N
      • UIKit (5)
      • SwiftUI (4)
      • 디자인 패턴 (2)
      • NumberterKit (2) N
    • 인프라 (Infrastructure) (1)
      • 도커 (Docker) (1)
      • NGINX (0)
    • 책 (1)
    • 기타 (6)
      • Error (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 큐
  • 백준
  • 스택
  • 그리디 알고리즘
  • ios
  • PS
  • SWIFT
  • 정렬
  • BOJ
  • 스위프트
  • DP
  • 자료구조
  • 문제해결
  • 이분 탐색
  • 그리디
  • apple
  • 알고리즘
  • Data Structure
  • 투 포인터
  • 자료 구조

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
Dev_Ted
[백준(BOJ)] 16401 과자 나눠주기 - 스위프트 (Swift)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.