글 읽기 - 테스트 케이스 다 해봤는데 바로 틀렸다고 나옵니다.

masioka 6년 전 1

a배열은 각 층의 값, 입력을 받는 배열입니다.

f배열은 각층의 마지막 번호를 저장한 배열입니다.

m배열은 dp값을 저장하는 배열입니다. ( f[500] = 125250 )

dp 점화식은 다음과 같습니다.

왼쪽 끝: m[i] = a[i] + m[i - (floor - 1)]

오른쪽 끝: m[i] = a[i] + m[i - floor]

중간: m[i] = a[i] + MAX( m[i - (floor - 1)], m[i - floor] )

문제는 이런식으로 풀었습니다.

IOI 대회 TC 모두 맞았고, 질문 중에 올라와있는 500 입력짜리 TC도 맞았습니다.

그런데 채점 시작하자마자 틀렸다고 뜨네요.

이유를 모르겠습니다. 도와주세요 형님들..

#include <stdio.h>
#define max(a,b) (a>b)?(a):(b)

char a[125251];
int f[501], m[125251];

void dp(int floor, int x) {
	if (x == f[floor - 1] + 1) {
		m[x] = a[x] + m[x - floor + 1];
	}
	else if (x == f[floor]) {
		m[x] = a[x] + m[x - floor];
	}
	else {
		int t = max(m[x - floor + 1], m[x - floor]);
		m[x] = a[x] + t;
	}
}

int main() {
	int n, i, j, res = 0;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		f[i] = i + f[i - 1];
	}
	for (i = 1; i <= n; i++) {
		for (j = f[i - 1] + 1; j <= f[i]; j++) {
			scanf("%d", &a[j]);
			dp(i, j);
		}
	}
	for (i = f[n - 1] + 1; i <= f[n]; i++) {
		res = max(res, m[i]);
	}
	printf("%d", res);
}

djm03178 6년 전 1

일단, 아직 확실치는 않지만 데이터에 수가 char형에 담을 수 없는 경우가 첫 케이스부터 있는 것 같습니다. int로 바꾸어 제출하니 정답이 뜹니다. 이건 좀 더 확인을 해보겠습니다.

그리고 char형 배열에 %d로 담는 건 안전하지 않습니다. scanf가 무조건 int 크기만큼을 목적지에 쓰기 때문에 주변의 바이트들도 함께 쓰여지기 때문입니다.

masioka 6년 전 0

제 생각에는 메모리 아끼자고 char형 쓴건데.. 역시 자료형은 용도를 맞게 써야겠네요.. 도움 감사합니다.

djm03178 6년 전 1

문제 조건에는 입력 범위가 0~99니

int x;

scanf("%d", &x);

a[j] = x;

라고만 해도 문제 없이 정답이 되어야 하겠지만, 일단은 데이터 상에 문제가 있는 듯해서 수정 요청을 했습니다.

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

문제

문제

출처

ICPC

테스트 케이스 다 해봤는데 바로 틀렸다고 나옵니다.

masioka 6년 전 1

djm03178 6년 전 1

masioka 6년 전 0

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말