글 읽기 - 똑같은 방식으로 풀었는데 C는 맞고 파이썬은 시간초과인 이유가 뭘까요

kdw9502 5년 전 0

같은 방법으로 풀었는데 C는 정답이고 파이썬은 시간초과가 뜨네요

어디서 시간을 낭비했을까요? 입력을 받으면서 최대값을 구하는 C 와 입력을 다 받고 최대값을 다시 구하는 차이일까요?

n,m = map(int,input().split())
trees = list(map(int,input().split()))

high = max(trees)
low = 0
while low<high:
    mid = (low+high)//2
    s=0
    for tree in trees:
        s += max(tree-mid,0)
    if s < m:
        high = mid-1
    elif s > m :
        low =mid
print(low)

kdw9502 5년 전 0

제출한 c코드입니다.

#include <stdio.h>

#define MAX(a,b) (a)>(b)? (a):(b)
long long a[1000002];
int main(void) {
	long long m,n;
	long long max=0;
	scanf("%lld %lld",&n,&m);
	for(long long i=0;i<n;i++){
		scanf("%lld",&a[i]);
		max = MAX(max,a[i]);
	}
	long long low=0,high=max,sum,mid;
	while (low<high){
		sum=0;
		mid = (low+high+1)/2;
		for(long long i=0;i<n;i++){
			sum += MAX(a[i]-mid,0);
		}
		if(sum<m){
			high = mid -1;
		}
		else{
			low = mid;
		}
	}
	printf("%lld",low);
}
	

jh05013 5년 전 0

파이썬은 옳은 해법이 시간초과 되어도 이상하지 않은 언어입니다.

파이썬과 똑같은데 훨씬 빠른 Pypy로 제출해 보세요.

luke0201 5년 전 1

Python의 입력 속도가 C언어보다 느려서 그럴 가능성이 높습니다. 특히 이 문제같은 경우는 나무의 개수가 100만개나 되니까요. input을 아래와 같이 재정의하시면 성능이 좋아집니다.

import sys


def input():
    return sys.stdin.readline().strip()

jh05013 5년 전 0

N개의 줄을 읽는 게 느릴 뿐이지 길이가 긴 하나의 줄을 읽는 건 input도 충분히 빠릅니다.

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

문제

문제

출처

ICPC

똑같은 방식으로 풀었는데 C는 맞고 파이썬은 시간초과인 이유가 뭘까요

kdw9502 5년 전 0

kdw9502 5년 전 0

jh05013 5년 전 0

luke0201 5년 전 1

jh05013 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말