글 읽기 - 10448 유레카 질문입니다!!! 도움!!!!!!!

mts90 5년 전 1

제 코드를 보면 케이스가 8개 정도 나와서 이렇게 풀었는데요...

search 함수를 저렇게 안짜고 반복문이나 재귀로 어떻게 풀 수 있을까요??

다이나믹 문제 풀 때도 이런식으로 배열을 몇 번씩 써야하는 문제는 못풀었습니다...

도와주세요!!!

#include<stdio.h>

int tri[1000];
int k;


int search (int i,int j,int n)
{
	int sum;

	sum=tri[i]*3;
	if (sum == k)
		return 1;
	sum=tri[i]*2+tri[j];
	if (sum == k)
		return 1;
	sum=tri[i]*2+tri[n];
	if (sum == k)
		return 1;
	sum=tri[i]+tri[j]*2;
	if (sum == k)
		return 1;
	sum=tri[i]+tri[j]+tri[n];
	if (sum == k)
		return 1;
	sum=tri[i]+tri[n]*2;
	if (sum == k)
		return 1;
	sum=tri[j]*3;
	if (sum == k)
		return 1;
	sum=tri[j]*2+tri[n];
	if (sum == k)
		return 1;
	sum=tri[j]+tri[n]*2;
	if (sum == k)
		return 1;
	sum=tri[n]*3;
	if (sum == k)
		return 1;

	else if (sum != k)
		return 0;
}

int main(void)
{
	int t;
	int i,j,n;
	int num;

	tri[0]=1;
	for (i=1;i<=1000;i++)
	{
		tri[i]=tri[i-1]+(i+1);
	}


	scanf("%d",&t);

	while (t)
	{
		scanf("%d",&k);

		for (i=0;i<k;i++)
		{
			for (j=i+1;j<k;j++)
			{		
				for (n=j+1;n<k;n++)
				{	
					num=search(i,j,n);
					if(num==1)
					{
						puts("1"); i=k; j=k; n=k; 
					}
				}
			}
		}
		if (num==0)
		{
			puts("0");
		}
		t--;
	}
	return 0;
}

portableangel 5년 전 1

사실 범위 [3,1000] 내에서 답이 0인 경우는 4 6 11 20 29 다섯 가지밖에 없습니다.

나머지 경우에 모두 1이 나오는지 테스트해보세요.

1000 이하인 삼각수가 몇 개나 될 지 생각해보시고, 더 간단하고 짧은 브루트 포스 솔루션을 작성해보시면 좋을 것 같습니다.

mts90 5년 전 0

portableangel님 감사합니다

답은 맞는데 알고리즘 생각하는게 어렵네요 ㅜㅜ

붕어빵 같은 문제는 정말 못풀겠네요...

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

문제

문제

출처

ICPC

10448 유레카 질문입니다!!! 도움!!!!!!!

mts90 5년 전 1

portableangel 5년 전 1

mts90 5년 전 0

portableangel님 감사합니다

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말