[백준 15035] I Work All Day (C#, C++) - soo:bak

문제 링크

15035번 - I Work All Day

설명

가능한 절단 높이들 중 하나를 골라 나무를 계속 잘랐을 때, 남는 길이를 최소화하는 높이를 구하는 문제입니다.

접근법

각 높이로 나무를 자르면 나무 길이를 높이로 나눈 나머지만큼 낭비됩니다.

모든 후보 높이에 대해 낭비를 계산하고 최소인 높이를 출력하면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
    var idx = 0;

    var n = int.Parse(parts[idx++]);
    var heights = new int[n];
    for (var i = 0; i < n; i++) heights[i] = int.Parse(parts[idx++]);
    var t = int.Parse(parts[idx++]);

    var bestWaste = int.MaxValue;
    var bestH = heights[0];
    for (var i = 0; i < n; i++) {
      var waste = t % heights[i];
      if (waste < bestWaste) {
        bestWaste = waste;
        bestH = heights[i];
      }
    }

    Console.WriteLine(bestH);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi h(n);
  for (int i = 0; i < n; i++) cin >> h[i];
  int t; cin >> t;

  int bestWaste = INT_MAX;
  int bestH = h[0];
  for (int i = 0; i < n; i++) {
    int waste = t % h[i];
    if (waste < bestWaste) {
      bestWaste = waste;
      bestH = h[i];
    }
  }

  cout << bestH << "\n";

  return 0;
}