글 읽기 - 1660번 질문이요.

rlejr135 9년 전 0

주석은 확인좀 하려고 달아둔거니 무시해주시고..

dy에다 1층 사면체에는 1개가 필요하고, 2층 사면체에는 4개가 필요하고, 3층에는 10개.. 이런 식으로 저장한 후

n개의 대포알로 가장 크게 만들 수 있는 사면체부터 만들며 대포알 숫자를 점점 줄여나갔는데

다른 예가 있나요? 아니면 제가 문제 자체를 잘못 이해한 건가요?

#include <cstdio>

int dy[135] = {0};
int main()
{
	int n;
	scanf("%d", &n);
	dy[0] = 0;
	dy[1] = 1;
	for (int i = 2; i <= 134; i++){
		dy[i] = dy[i - 1] + i;
		dy[i - 1] += dy[i - 2];
		//printf("%d\n", dy[i - 1]);
	}
	int cnt = 0;
	while (n != 0)
	{
		int i;
		for (i = 1; i <= 134; i++)
		{
			if (n < dy[i])
				break;
		}
		//printf("[%d][%d]\n", n, dy[i - 1]);
		n -= dy[i - 1];
		cnt++;
	}
	printf("%d\n", cnt);
	return 0;
}

lll4592 9년 전 1

동전 문제와 유형이 같습니다. 1원 5원 11원이 있을때 큰거부터 주면 답이 5이지만 5원을 3개 를 주는 더 최적인 경우가 존재하죠. 따라서 이 문제는 그리디 알고리즘이 아닌 다이나믹 프로그래밍으로 문제를 해결해야 합니다.

kesakiyo 9년 전 6

소스를 보면 현재 가지고 있는 대포알에서

만들 수 있는 가장 큰 사면체 모양의 대포알만큼 빼는 코드를 작성하셨네요.

이러한 그리디 방식으로는 문제에서 요구하는 답을 구하지 못해요.

파워 반례를 들자면 인풋이 40이라고 할 때 rlejr135님의 코드는

만들 수 있는 사면체의 최소 수가 3이라고 답을 합니다.

하지만 20개의 대포알을 사용하는 4층짜리 사면체 두개로 40개를 모두 사용할 수 있습니다.

때문에 답은 2가 되어야 하죠.

rlejr135 9년 전 0

아 그렇구나

감사합니다!

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

문제

문제

출처

ICPC

1660번 질문이요.

rlejr135 9년 전 0

lll4592 9년 전 1

kesakiyo 9년 전 6

rlejr135 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말