글 읽기 - 숫자삼각형 반례가 무엇일까요 ㅠㅠ

glow153 7년 전 0

제가 해볼 수 있는 케이스는 다 해도 맞게 나오는데 채점에는 틀렸다고 나오네요 ㅠㅠ

#include <stdio.h>

int max2i(int a, int b){
	return (a>b)?a:b;
}
int main(void){
	int iaaInput[500][500]={0};
	int dpTable[500][500]={0};
	int iTriangleSize;

	scanf("%d",&iTriangleSize);
	for(int i=0; i<iTriangleSize; i++)
		for(int j=0; j<=i; j++)
			scanf("%d",&iaaInput[i][j]);

	for(int i=0; i<iTriangleSize; i++){ //make dp table
		for(int j=0; j<=i; j++){
			if(j==0)
				dpTable[i][j] = dpTable[i-1][j] + iaaInput[i][j];
			else if(j==i)
				dpTable[i][j] = dpTable[i-1][j-1] + iaaInput[i][j];
			else
				dpTable[i][j] = max2i(dpTable[i-1][j-1], dpTable[i-1][j])
					+ iaaInput[i][j];
		}
	}

	int max = dpTable[iTriangleSize-1][0];
	for(int i=1; i<iTriangleSize; i++){	//find maximum number
		if(max < dpTable[iTriangleSize-1][i])
			max = dpTable[iTriangleSize-1][i];
	}

	printf("%d\n",max);

	return 0;
}

sait2000 7년 전 0

8번 줄을 아래와 같이 고치면 해결됩니다... 이유는 저도 아직 모르겠어요 같이 고민해봐요

	int dpTable[500][501]={0};

sait2000 7년 전 0

1932_input_large.txt

반례로 이런 게 있습니다. 36831이 답인데 36897이 나오네요.

sait2000 7년 전 0

지금 보니까 gcc로 컴파일할 때 500줄 짜리 삼각형은 최적화 수준에 따라 답이 다르게 나옵니다!... -O0 (최적화 안함)일 때는 답이 맞게 나오는데 -O2일 때는 뭔가 조금 더 크게 나오네요.

glow153 7년 전 0

sait2000 제 소스 꼼꼼이 잘 봐주셔서 감사해요! 말씀하신대로 고쳤는데 여전히 안되네요 ㅠㅠ

그리고 반례 txt 봤는데요 문제에서 제시한 조건은 삼각형의 크기가 500 이하라서 안맞지 않나요?

sait2000 7년 전 0

이상하네요 이대로 넣어서 맞았습니다 나왔는데
문제 입력 설명에 '첫째 줄에 삼각형의 크기 n(1≤n≤500)이 주어지고'라고 써있으니까 맞을 걸요

#include <stdio.h>

int max2i(int a, int b){
	return (a>b)?a:b;
}
int main(void){
	int iaaInput[500][500]={0};
	int dpTable[500][501]={0};
	int iTriangleSize;

	scanf("%d",&iTriangleSize);
	for(int i=0; i<iTriangleSize; i++)
		for(int j=0; j<=i; j++)
			scanf("%d",&iaaInput[i][j]);

	for(int i=0; i<iTriangleSize; i++){ //make dp table
		for(int j=0; j<=i; j++){
			if(j==0)
				dpTable[i][j] = dpTable[i-1][j] + iaaInput[i][j];
			else if(j==i)
				dpTable[i][j] = dpTable[i-1][j-1] + iaaInput[i][j];
			else
				dpTable[i][j] = max2i(dpTable[i-1][j-1], dpTable[i-1][j])
					+ iaaInput[i][j];
		}
	}

	int max = dpTable[iTriangleSize-1][0];
	for(int i=1; i<iTriangleSize; i++){	//find maximum number
		if(max < dpTable[iTriangleSize-1][i])
			max = dpTable[iTriangleSize-1][i];
	}

	printf("%d\n",max);

	return 0;
}

glow153 7년 전 0

sait2000 실수가 좀 있었네요! 정말 감사합니다!!

텍스트파일 열었을 때 맨 윗줄에 500323 이라고 되어있어서 50만이 넘는 삼각형을 만드신줄 알았는데ㅋㅋ 알고보니 엔터키가 어쩐일인지 삭제된 모양이군요

500과 501의 차이가 무엇인지 정말 궁금하긴 하네요ㅠㅋㅋ 맞았지만 찜찜한 이기분...

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

문제

문제

출처

ICPC

숫자삼각형 반례가 무엇일까요 ㅠㅠ

glow153 7년 전 0

sait2000 7년 전 0

sait2000 7년 전 0

sait2000 7년 전 0

glow153 7년 전 0

sait2000 7년 전 0

glow153 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말