글 읽기 - 제발 반례 좀 부탁드립니다 ㅜㅜ

xaemin 5년 전 0

반례 부탁드립니다 ㅜㅜ
여기 질문글 모두 다 읽어보고 https://ioinformatics.org/page/ioi-1994/20 여기 사이트도 가서 봤는데
반례를 하나도 못 찾겠습니다.

기본 인풋을 포함해서 제가 해본건 모두 다 잘 되는데 왜 실패라고 나오는지 모르겠는데, 혹시 반례를 알려주실 분 계실까요?

#include <stdio.h>

long long max[501][501];
long long cost[501][501];

long long GetMax(long long a, long long b) {
	return a > b ? a : b;
}

long long GetMaxSum(int row, int col) {
	if (row == 0) {
		max[row][col] = cost[row][col];
	}
	else if (max[row][col] != -1) {
		
	}
	else {
		if (col == 0) { // left end
			max[row][col] = GetMaxSum(row - 1, col) + cost[row][col];
		}
		if (col == row) { // right end
			max[row][col] = GetMaxSum( row - 1, col - 1) + cost[row][col];
		}
		else { // and the rest
			max[row][col] = GetMax(GetMaxSum(row - 1,col - 1), GetMaxSum(row - 1,col)) + cost[row][col];
		}		
	}
	return max[row][col];
}
int main() {
	int numLine;
	scanf("%d", &numLine);

	//init
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < 500; j++) {
			max[i][j] = -1;
		}
	}

	// input
	for (int i = 0; i < numLine; i++) {
		for (int j = 0; j < i + 1; j++) {
			scanf("%d", &cost[i][j]);
		}
	}

	// calc
	for (int i = 0; i < numLine; i++) {
		GetMaxSum(numLine, i);
	}

	// get final max 
	long long resMax = 0;
	for (int i = 0; i < numLine; i++) {
		if (max[numLine][i] > resMax)
			resMax = max[numLine][i];
	}

	printf("%lld\n", resMax);
	
	return 0;
}

luniro 5년 전 0

i의 범위는 0부터 numLine -1까지인데, 50, 56, 57번째 줄에서 numLine 대신 numLine - 1을 쓰면 되지 않을까요?

xaemin 5년 전 0

감사합니다 luniro닙! numLine을 numLine-1으로만 바꿔도 잘 되네요 ㅜㅜ

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

문제

문제

출처

ICPC

제발 반례 좀 부탁드립니다 ㅜㅜ

xaemin 5년 전 0

luniro 5년 전 0

xaemin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말