글 읽기 - 3시간째 틀린 테스트케이스만 찾고 있네요 ㅠㅠ 무엇이 문제일 까요..?

kimgo3282 8년 전 0

dp를 이용해서 음수일 경우도 생각해서 풀었는데.. 무엇이 틀린것 일까요.. 멘붕이네요..

#include<stdio.h>
#define MAX 987654321

int testCase;
int map[100001][3];
int cache[100001][3];
int x, y;

int min(int a, int b) {
	return a < b ? a : b;
}

int dp(int dx, int dy) {
	if (dx == 1) {
		if (dy == 0) {
			return cache[dx][dy] = map[dx][dy] + map[0][1];
		}
		if (dy == 1) {
			return cache[dx][dy] = min(min(dp(1, 0), map[0][1]),map[0][1] + map[0][2]) + map[dx][dy];
		}
		if (dy == 2) {
			return cache[dx][dy] = min(min(dp(1, 1), map[0][1]), map[0][1] + map[0][2]) + map[dx][dy];
		}
	}

	if (cache[dx][dy] != MAX)
		return cache[dx][dy];

	if (dy == 0) {
		return cache[dx][dy] = min( dp(dx - 1, 0), dp(dx - 1, 1) ) + map[dx][dy];
	}
	else if (dy == 1) {
		return cache[dx][dy] = min(dp(dx, 0),min(min(dp(dx - 1, 0), dp(dx - 1, 1)), dp(dx - 1, 2))) + map[dx][dy];
	}
	else {
		return cache[dx][dy] = min(dp(dx, 1), min(dp(dx - 1, 1), dp(dx - 1, 2))) + map[dx][dy];
	}	
}

int main() {
	int n, t, a,b,c;

	scanf(" %d", &testCase);

	for (n = 1; n <= testCase; n++) {
		for (int i = 0; i < 100001; i++) {
			for (int j = 0; j < 3; j++) {
				cache[i][j] = MAX;
			}
		}
		x = -1;		
		y = 0;
		while (1) {
			scanf(" %d", &t);			

			if (t == 0 && y%3 ==0 && x>0) break;

			if (y % 3 == 0) {				
				x++;
			}
			map[x][y % 3] = t;
			y++;
		}		
		printf("%d. %d\n", n,dp(x, 1));
	}
	return 0;
}

kimgo3282 8년 전 0

죄송합니다. 문제를 잘못 읽었네요.

처음 주어지는 값이 테스트 케이스 숫자인줄 알았는데 행의 크기 였네요..

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

문제

문제

출처

ICPC

3시간째 틀린 테스트케이스만 찾고 있네요 ㅠㅠ 무엇이 문제일 까요..?

kimgo3282 8년 전 0

kimgo3282 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말