[Baekjoon]백준 2805 나무 자르기(실버 2) - Python, C++

문제설명 1

문제설명 2

문제를 살펴보면 이전에 풀이한 문제(백준 1654 랜선 자르기)와 유사하다

이번에는 나무를 잘라서 들고가야하는데, 그 자른 나무의 총 길이의 합이 목표치가 되도록 설정하여야한다

저번 문제에서처럼 start, end를 각각 1과 나무의 최대 길이로 설정하여주었다

이후 while문을 통해 자르고 난 후의 나무의 길이를 변수에 저장해주면 된다 대신 여기서 주의하여야할 점은

저번 문제에서는 나눈 몫을 더하였지만 이번에는 잘랐을 때의 나무의 길이를 더해주어야한다는 점이다

이를 고려하지 않았고, 잘못된 코드를 제출하였다

Tree_num, need_length = map(int, input().split())
Tree = list(map(int, input().split()))

start, end = 1, max(Tree)
while start <= end:
    mid = (start + end) // 2
    get_Tree = 0
    for tr in Tree:
        if tr // mid >= 1: # 나무가 잘리는 경우
            get_Tree += tr % mid
    if get_Tree >= need_length: # 더 많은 나무를 가지게 되는 경우
        start = mid + 1
    else: # 목표치보다 더 작은 나무를 가지게 되는 경우
        end = mid - 1
        
print(end)

예제로 주어진 경우는 최종 출력값이 같게 나오지만, get_Tree에 저장되는 값을 나머지연산 후의 결과로 해둬서

다른 예제의 경우에는 오류가 발생할 것이다 40인 나무를 12로 잘랐다고 가정하면 잘못된 코드에서는 4가 나온다

그래서 if문이 있는 부분을 수정하여 빼기로 수정하였으나 이번에는 시간초과가 계속해서 발생하였다

검색을 해보았더니 따로 코드가 존재하는 것은 아니었고, PyPy3로 제출하였더니 맞았습니다!를 확인할 수 있었다

 

해당 코드를 C++로도 작성을 해보았는데, 파이썬 코드로 먼저 작성을 한 후에 C++로 작성을 하였더니

자료형 범위에 대한 고려를 적절하게 하지 않았고, 그로 인하여 수많은 제출을 하게 되었다

이제부터는 C++ 코드로 먼저 작성을 완료한 후에 Python으로 작성해야겠다는 생각이 들게 된 문제였다

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int Tree_num, need_length;
    cin >> Tree_num >> need_length;

    vector<int> Tree(Tree_num);
    for(int i = 0; i < Tree_num; i++) {
        cin >> Tree[i];
    }
    long long start = 1;
    long long end = *max_element(Tree.begin(), Tree.end());
    int result = 0;
    while(start <= end) {
        long long mid = (start + end) / 2;
        long long get_Tree = 0;
        for(int i = 0; i < Tree_num; i++) {
            if(Tree[i] > mid) // 나무가 잘리는 경우
                get_Tree += Tree[i] - mid;
        }
        if(get_Tree >= need_length) {// 더 많은 나무를 가지게 되는 경우
            start = mid + 1;
        }
        else // 목표치보다 더 작은 나무를 가지게 되는 경우         
            end = mid - 1;
    }

    cout << end << endl;

    return 0;
}