글 읽기 - 틀렸는데, 반례를 찾고 싶네요.

lakshimi 4년 전 0

이분 탐색을 이용했고요. 최고 값을 n*10000 으로 무식하게 크게 잡았습니다.

m 값을 넘는지 아닌지 검사하기 위해서는 시뮬레이션을 했고요.

특별하게 문제 없다고 생각했고, 나름 반례를 만들어서 넣어보았는데, 이유를 모르겠네요.

숫자 범위는, 최대 N 값이 100,000, 최대 일 사용금액이 10,000이니까, int 범위를 벗어나지 않는다고 판단했습니다.

#include <stdio.h>

int main()
{
	int n, m, v[100000], i, j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++) scanf("%d",v+i);
	for(i=0,j=n*10000;i<j-1;)
	{
		int c=(i+j)/2, t=0, r=0;
		for(int k=0;k<n;k++)
		{
			if(t>=v[k]) { t-=v[k]; continue; }
			t=c-1-(v[k]-1)%c;
			r+=(v[k]+c-1)/c;
		}
		if(r<=m) j=c; else i=c;
	}
	printf("%d\n", j);
}

lakshimi 2년 전 0

하루에 쓸 수 있는 금액 K 금액 이상으로 하루 사용금액이 들어가있지 않아야하는군요.

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

문제

문제

출처

ICPC

틀렸는데, 반례를 찾고 싶네요.

lakshimi 4년 전 0

lakshimi 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말