글 읽기 - 1421 나무꾼 이다솜 질문입니다.

cubalys 6년 전 2

완전탐색으로 풀었습니다.

sum = 총 단위 수

ccum = 자르는 횟수

ssum = 못 쓰는 단위 수

크기 1로 자를 때 ~ 10000으로 자를 때까지 전부 얼만큼의 이득을 볼 수 있는지를 계산 한 후

가장 큰 값을 출력하도록 했습니다.

1000 * 10000으로 시간복잡도 상으로도 문제가 없을 것이라 생각했습니다.

전부 탐색하는 것이라 틀린 부분이 없어 보이는데 어떤 부분이 잘못된건지 잘 모르겠습니다.

접근 방법이 잘못된걸까요?

#include <cstdio>
int main(){
	int N, C, W, map[1001], sum = 0, ssum = 0, csum = 0, max = 0;
	scanf("%d%d%d", &N, &C, &W);
	for (int i = 0; i < N; i++)
		scanf("%d", &map[i]), sum += map[i];
	for (int i = 1; i <= 10000; i++){
		csum = ssum = 0;
		for (int j = 0; j < N; j++){
			csum += (map[j] - 1) / i;
			ssum += map[j] % i;
		}
		int tmp = (sum - ssum) * W - csum * C;
		if (tmp > max)
			max = tmp;
	}
	printf("%d\n", max);
}

an2416 6년 전 11

예외 발생

4 1000 1

2 1 1 1

코드 로직상 길이1로만 구성하였을 경우 -> (5 - 1000) 이라는 계산식이 발생합니다.

하지만 실제 정답은 길이2인 나무를 팔지않고 길이1인 나무를 3개팔아 3이 정답이 되어야합니다.

cubalys 6년 전 0

감사합니다

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

문제

문제

출처

ICPC

1421 나무꾼 이다솜 질문입니다.

cubalys 6년 전 2

an2416 6년 전 11

cubalys 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말