글 읽기 - 4883번 삼각 그래프

waylight3 8년 전 0

DP로 풀려고 했는데 한 75%쯤 채점하다가 틀렸다고 나오는 걸 보니 이 코드가 통과 못하는 테스트 케이스가 있나봅니다.

음수가 입력될 수 있다는 건 알고 있는데 그건 어차피 min이 알아서 작은 값을 찾아주니 문제가 없을 것 같구요.

제가 아무리 케이스를 만들어서 넣어봐도 제가 손으로 계산한거랑 같은 답이 나오는데 혹시 제가 뭘 잘못 생각하고 있나 해서 질문합니다.

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int graph[100000][3];
int cache[100000][3];

int solve(int y, int x)
{
	int& ret = cache[y][x];
	
	if (ret != -1) return ret;

	if (y == n - 2)
	{
		if (x == 0)
		{
			return ret = min(solve(y, 1), min(solve(y + 1, 0), solve(y + 1, 1))) + graph[y][x];
		}
		if (x == 1)
		{
			return ret = min(solve(y + 1, 0), solve(y + 1, 1)) + graph[y][x];
		}
		if (x == 2)
		{
			return ret = graph[y + 1][1] + graph[y][x];
		}
	}
	if (y == n - 1)
	{
		if (x == 0)
		{
			return ret = graph[y][0] + graph[y][1];
		}

		return ret = graph[y][1];
	}
	if (x == 0)
	{
		return ret = min(solve(y, 1), min(solve(y + 1, 0), solve(y + 1, 1))) + graph[y][x];
	}
	if (x == 1)
	{
		return ret = min(solve(y, 2), min(min(solve(y + 1, 0), solve(y + 1, 1)), solve(y + 1, 2))) + graph[y][x];
	}
	if (x == 2)
	{
		return ret = min(solve(y + 1, 1), solve(y + 1, 2)) + graph[y][x];
	}
}

int main()
{
	int test = 1;

	while (true)
	{
		cin >> n;

		if (n == 0) { break; }

		for (int i = 0; i < n; i++)
		{
			cache[i][0] = cache[i][1] = cache[i][2] = -1;
		}

		for (int i = 0; i < n; i++)
		{
			cin >> graph[i][0] >> graph[i][1] >> graph[i][2];
		}

		cout << test << ". " << solve(0, 1);
	}
	
    return 0;
}

rhs0266 8년 전 0

test 값 증가 하셨나요?

waylight3 8년 전 0

test++로 바꿔도 틀리네요 ㅠㅠ

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

문제

문제

출처

ICPC

4883번 삼각 그래프

waylight3 8년 전 0

rhs0266 8년 전 0

waylight3 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말