[백준] 3649 - 로봇 프로젝트

1. 문제

3649번: 로봇 프로젝트

2. 개요

로봇을 만들던 도중 생긴 구멍을 막기 위해 레고 두 조각이 필요하다.

구멍은 x센티미터이고, 레고 두 조각의 너비의 합이 꼭 x센티미터여야 한다.

레고 조각들의 수와 너비들이 나노미터로 주어졌을 때 구멍을 막을 수 있는지의 여부와 막을 수 있다면 막을 수 있는 두 레고 조합 (a, b)중 b - a가 가장 큰 조합을 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

레고 조각들의 너비가 나노미터로 주어지기 때문에 구멍의 단위를 맞춰준다.

입력받은 레고 조각들을 오름차순 정리한 뒤 가장 짧은 레고조각부터 기준으로 잡고 이분탐색을 시작한다.

x에 딱 맞는 조각의 짝이 존재한다면, 가장 짧은 레고조각부터 진행했기 때문에 다른 조합을 탐색할 필요가 없어진다. 따라서 탈출하여 이를 답으로 출력한다.

3-2. Python

import sys

while True:
    x = sys.stdin.readline().rstrip()

    if x == "":
        break

    x = int(x) * 10000000

    n = int(sys.stdin.readline())

    legos = []

    for i in range(n):
        legos.append(int(sys.stdin.readline()))

    legos.sort()

    l = 0
    shortest = -1
    longest = -1
    cando = False

    while l < n - 1 and cando == False:
        start, end = l + 1, n - 1

        while start <= end and cando == False:
            mid = (start + end) // 2

            if legos[l] + legos[mid] == x:
                shortest = legos[l]
                longest = legos[mid]
                cando = True

            elif legos[l] + legos[mid] < x:
                start = mid + 1

            else:
                end = mid - 1

        l += 1

    if cando:
        print("yes", shortest, longest)

    else:
        print("danger")

3-3. C#

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

            while (true)
            {
                try
                {
                    int x = int.Parse(sr.ReadLine());

                    x *= 10000000;

                    int n = int.Parse(sr.ReadLine());

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

                    for (int i = 0; i < n; i++)
                        legos.Add(int.Parse(sr.ReadLine()));

                    legos.Sort();

                    int l = 0;
                    int shortest = -1;
                    int longest = -1;
                    bool cando = false;

                    while (l < n - 1 && !cando)
                    {
                        int start = l + 1;
                        int end = n - 1;

                        while (start <= end && !cando)
                        {
                            int mid = (start + end) / 2;

                            if (legos[l] + legos[mid] == x)
                            {
                                cando = true;
                                shortest = legos[l];
                                longest = legos[mid];
                            }

                            else if (legos[l] + legos[mid] < x)
                                start = mid + 1;

                            else
                                end = mid - 1;
                        }

                        l++;
                    }

                    if (cando)
                        sw.WriteLine($"yes {shortest} {longest}");

                    else
                        sw.WriteLine("danger");
                }

                catch
                {
                    sw.Close();
                    break;
                }
            }
        }
    }
}