글 읽기 - 삼각그래프.. 왜 틀렸을까요.

star7sss 7년 전 0

정말 예외 케이스가 무엇인지 못 찾겠습니다.

음수를 넣어도 돌아가는 데......... 고수님들 부탁드립니다.

#include <stdio.h>

int grape[100001][3];
int min(int, int, int);
int min2(int, int);

int main()
{
	int row, i,j,k=0;
	int Sa=0, Sb=0, Sc=0;
	int Ta = 0, Tb = 0, Tc = 0;

	while(1)
	{
		scanf("%d", &row);
		if (row == 0)
			break;
		for (i = 0; i < row; i++)
		{
			for (j = 0; j < 3; j++)
				scanf("%d", &grape[i][j]);
		}

		for (i = 0; i < row; i++)
		{
			if (i == 0)
				Sa = grape[i][1], Sb = grape[i][1], Sc = grape[i][1];
			else
			{
				Ta = grape[i][0] + min2(Sa, Sb);
				Tb = grape[i][1] + min(Sa, Sb, Sc);
				Tc = grape[i][2] + min2(Sb, Sc);
				Sa = Ta, Sb = Tb, Sc = Tc;
			}
		}
		printf("%d %d\n", ++k, Tb);
		
		Sa = 0, Sb = 0, Sc = 0, Ta = 0, Tb = 0, Tc = 0;
	}
}

int min(int a, int b, int c)
{
	if (b <= a && b <= c)
		return b;
	if (a <= b && a <= c)
		return a;
	return c;
}

int min2(int a, int b)
{
	if (a <= b)
		return a;
	return b;
}

kookmin20103324 7년 전 1

점화식을 진행하기 위해 설정하는 초기값 (i == 0) 부분을 다시 확인해 보세요.

문제의 조건대로라면, 0,0 부분은 절대로 갈 수 없으므로 거리는 INF가 되며

0,1부분은 0,1값 그대로, 0,2 부분은 0,1+0,2 값을 가지고 시작을 해야합니다.

star7sss 7년 전 0

조언 정말 감사합니다....

말씀듣고 고쳤지만... 여전히 틀렸다고 나오네요.

정말 왜 틀렸을까요..

혹시 예외케이스 같은 게 있나요?

#include <stdio.h>

int grape[100001][3];
int min(int, int, int);
int min2(int, int);

int main()
{
	int row, i,j,k=0;
	int Sa=0, Sb=0, Sc=0;
	int Ta = 0, Tb = 0, Tc = 0;

	while(1)
	{
		scanf("%d", &row);
		if (row == 0)
			break;
		for (i = 0; i < row; i++)
		{
			for (j = 0; j < 3; j++)
				scanf("%d", &grape[i][j]);
		}
		Sa = grape[0][1], Sb = grape[0][1], Sc = grape[0][1];

		for (i = 0; i < row; i++)
		{
			if (i == 0)
			{
				if (grape[0][2] < 0) Sc += grape[0][2];
			}
			else
			{
				Ta = grape[i][0] + min2(Sa, Sb);
				Tb = grape[i][1] + min(Sa, Sb, Sc);
				Tc = grape[i][2] + min2(Sb, Sc);
				Sa = Ta, Sb = Tb, Sc = Tc;
			}
		}
		printf("%d %d\n", ++k, Tb);
		
		Sa = 0, Sb = 0, Sc = 0, Ta = 0, Tb = 0, Tc = 0;
	}
}

int min(int a, int b, int c)
{
	if (b <= a && b <= c)
		return b;
	if (a <= b && a <= c)
		return a;
	return c;
}

int min2(int a, int b)
{
	if (a <= b)
		return a;
	return b;
}

kookmin20103324 7년 전 0

이글을 늦게 보게되었네요.. 알림이 뜨길 바라며

초기 점화식이 틀렸어요. Sa = grape[0][1], Sb = grape[0][1], Sc = grape[0][1]; 여기가 틀렸다는 거에요

Sa는 중앙값을 가지고 시작할 수 없고, 우측 값은 grape[0][0]+grape[0][1] 만을 가질수밖에 없어요.

그리고 중간 Ta Tb Tc도 경우의 수가 좀 더 많아요

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

문제

문제

출처

ICPC

삼각그래프.. 왜 틀렸을까요.

star7sss 7년 전 0

kookmin20103324 7년 전 1

star7sss 7년 전 0

kookmin20103324 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말