글 읽기 - C++17 70%에서 시간초과가 뜹니다

icantdie_imallin 2년 전 0

시간이 오래 걸리는 작업들을 최대한 쳐냈다고 생각했는데 여전히 시간 초과가 뜹니다...

채택한 방식은;

처음에 한 대 이상의 컴퓨터를 쌓아둔 칸의 컴퓨터 대수만 벡터에 저장합니다.

이후 while과 for문을 이용해 한 층씩 cur_computer(현재 정상 작동하는 컴퓨터 수)에 저장합니다.

계산하는 기준은 min_count(진행된 시간: 분)입니다.

어디에서 잘못 작성한 걸까요? 도움 부탁드립니다!

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

//17245
int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int num;
    cin >> num;
    long long total_computer = 0;
    vector<int> computer;
    for (int i = 0; i < num*num; ++i) {
        int c;
        cin >> c;
        if (c > 0) {
            total_computer += c;
            computer.push_back(c);
        }
    }

    long long cur_computer = 0;
    int min_count = 0;
    long long half_of_total = (double) total_computer / 2 + 0.5; //2로 나누므로 0.5를 더해주는 것으로 ceil을 대신할 수 있음. 
    vector<int>::iterator iter;
    while (cur_computer < half_of_total) {
        for (iter = computer.begin(); iter != computer.end(); ++iter) {
            if (*iter > min_count) {
                ++cur_computer;
            }
        }
        ++min_count;
    }

    cout << min_count; 
    return 0; 
} 

fccva 2년 전 1

시간이 오래 걸리는 최악의 경우를 생각해보세요

N×N칸에 모두 1000만대씩 들어갑니다.

이걸 한 층씩 올라가면서 찾으려면 너무 많은 시간이 필요합니다.

만약 찬공기가 x 층까지 왔는데도 작동하는 컴퓨터 수가 전체의 절반이 안된다면

x 이하의 층도 당연히 안됩니다.

만일 찬공기가 x 층까지 왔는데 작동하는 컴퓨터 수가 전체의 절반 이상이라면

x 이상의 층에서도 당연히 절반 이상입니다.

만일 x를 최대높이의 절반으로 잡는다면

위 사실을 이용하면 탐색할 범위를 절반씩 줄여나갈 수 있습니다.

icantdie_imallin 2년 전 0

@fccva

그렇네요! 이진 트리 카테고리 문제인데 이진 검색을 사용하지 않은 제 실책입니다..

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C++17 70%에서 시간초과가 뜹니다

icantdie_imallin 2년 전 0

fccva 2년 전 1

icantdie_imallin 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말