[백준] 14627 - 파닭파닭

1. 문제

14627번: 파닭파닭

2. 개요

길이가 일정하지 않은 파들을 이용해 같은 양의 파를 최대한 많이 넣어 일정 개수의 파닭을 만든다.

이렇게 파닭을 다 만든 후 남은 파의 길이를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

이분탐색을 이용한다.

1을 시작점 s, 가장 긴 파의 길이를 끝 점 e로 잡고 시작한다.

중간점인 m을 파닭에 넣을 파로 설정한다.

각 파의 길이를 m으로 나눈 값이 각 파로 만들 수 있는 파닭의 개수가 된다.

그러므로 이를 이용해 이분탐색을 진행하면 된다.

각 파의 길이를 m으로 나눈 값을 모두 더한 값이 파닭의 개수보다 크거나 같다면 파를 더 길게 자를 수 있으므로 m을 저장해두고 시작점 s를 m+1로 갱신한다.

그렇지 않다면 파닭의 개수를 맞출 수 없다는 얘기이므로 끝 점 e 를 m-1로 갱신한다.

반복문을 탈출했다면 전체 파의 길이 - 넣을 파의 길이 * 파닭의 개수를 답으로 출력한다.

3-2. Python

import sys

N, M = map(int, sys.stdin.readline().split())

gos = []
s, e = 1, 1
maxlength = 0
total = 0
answer = 0

for i in range(N):
    gos.append(int(sys.stdin.readline()))

    total += gos[i]

    if gos[i] > e:
        e = gos[i]

while s <= e:
    m = (s + e) // 2

    tmp = sum([g // m for g in gos])

    if tmp >= M:
        s = m + 1
        maxlenth = m

    elif tmp < M:
        e = m - 1

answer = total - maxlenth * M
print(answer)

3-3. C#

namespace boj_14627
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            long s = 1;
            long e = 1;
            long maxlength = 0;
            long total = 0;
            long answer = 0;

            List<int> gos = new List<int>();

            for (int i = 0; i < N; i++)
            {
                gos.Add(int.Parse(sr.ReadLine()));

                total += gos[i];

                if (gos[i] > e)
                    e = gos[i];
            }

            while (s <= e)
            {
                long m = (s + e) / 2;

                long tmp = 0;

                foreach (int g in gos)
                    tmp += g / m;

                if (tmp >= M)
                {
                    s = m + 1;
                    maxlength = m;
                }

                else
                    e = m - 1;
            }

            answer = total - maxlength * M;
            sw.WriteLine(answer);
            sw.Close();
        }
    }
}