문제
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
코드
using System;
using System.Text;
using System.Collections.Generic;
namespace dongsik
{
class Algorithm
{
static void Main(string[] str)
{
int[] input = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
int n = input[0];
int m = input[1];
int[] tree = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
long end = 0;
long start = 0;
foreach(int t in tree)
{
if(end < t) { end = t; }
}
while(start <= end)
{
long mid = (start + end)/2;
long sum = 0;
for(int i = 0; i < n; i++)
{
if(tree[i] > mid)
{
sum += tree[i] - mid;
}
}
if(sum >= m) { start = mid + 1; }
else { end = mid - 1; }
}
// 길이
Console.Write(end);
}
}
}
고민
노션에 이런 고민들을 해봤다.. 그리고 계속해서 정답이 틀렸는데, 이유가
1. return은 mid가 아니라 end다.
2. long타입으로 선언
왜 end인지는 뤼튼이 알려줬다.
어머! 얘. 내가 알려줄게 너가 말하려던게 이거 맞지? 이건 말이야~~ 백준 2805 문제는 이진 탐색을 활용하여 풀 수 있는 문제야. 코드를 보니 대체적으로 잘 작성한 것 같아. 하지만 한 가지 문제가 있어. 문제는 이진 탐색이 끝나고 난 후의 결과 출력 부분이야. `Console.Write(mid);`라고 써서 마지막으로 계산한 mid 값을 출력하도록 했는데, 실제로는 mid 값이 아니라 end 값을 출력해야 해. 왜냐하면 이진 탐색의 과정에서 mid 값을 사용해 나무의 높이를 계산하고, 그 결과가 필요한 나무의 길이보다 크거나 같으면 시작점을 mid+1로 옮기는 과정을 거치잖아? 그런데 만약 필요한 나무의 길이와 정확히 일치하는 높이를 찾지 못하고, 그보다 조금 더 많이 잘랐을 경우에는 mid 값이 실제로 사용 가능한 최대 높이보다 1이 더 큰 상태로 종료되게 돼. 그래서 맞는 값을 출력하려면 `Console.Write(end);`로 바꿔야 해. 그러면 이진 탐색이 끝났을 때의 최대 높이를 올바르게 출력할 수 있을거야.
음.. 그렇다면 while문에 조건을 넣는다면?
while(start <= end)
{
long mid = (start + end)/2;
long sum = 0;
for(int i = 0; i < n; i++)
{
if(tree[i] > mid)
{
sum += tree[i] - mid;
}
}
if(mid == m) { result = mid; break; }
if(sum >= m) { start = mid + 1; }
else { end = mid - 1; }
}
// 길이
Console.Write(result);
mid는 정답이 될 수 없는 것인지 고민하다가 위처럼 코드를 짰다. 하지만 실패
문제는 if(mid == m) { result = mid; break; } 이 부분이야. 이 코드는 이진 탐색의 중간 값(mid)이 목표로 하는 나무의 길이(m)과 같을 경우, 즉시 이진 탐색을 종료하도록 설계되어 있어.
하지만 이렇게 하면 문제가 생겨. 이 문제에서 나무의 길이와 중간값이 같다는 것이 곧 최적의 해라는 것을 보장하지 않아. 왜냐하면 mid 값이 m과 같더라도, 더 큰 mid 값에서도 m 이상의 나무를 얻을 수 있을지도 모르니까. 따라서 mid 값이 m과 같을 때 바로 종료하면 그보다 높은 높이에서 얻을 수 있는 결과를 놓칠 수 있어.
그렇다고 하네요...
이진탐색을 무조건 mid에만 포커스를 두었는데, 실제로는 end였다니.. 너무 충격적이라서 기억에 오래 갈 거 같다.
'동식이 취업시키기 작전 > 코딩테스트' 카테고리의 다른 글
[백준] 10815 숫자카트(C#) (0) | 2024.02.04 |
---|---|
[백준] 1654 랜선 자르기(C#) (1) | 2024.02.02 |
[백준] 1920 수 찾기(C#) (0) | 2024.01.31 |
[백준] 2309번 일곱 난쟁이 (1) | 2024.01.30 |
[백준] 1436 영화감독 숌(C#) (1) | 2024.01.29 |