글 읽기 - 알고리즘이 틀린 건가요?

ainch96 7년 전 0

단순한 dp라고 생각 했는데 dp가 아닌 건가요? 아니면 고려하지 않은 경우가 존재한 건가요 ???

#include <stdio.h>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 100005;

ll dp[N][3];
ll a[N][3];

int main(){
	int test=0;
	while(1){
		int n;
		scanf("%d",&n);
		if(n==0)break;

		for(int i=0;i<n;++i){
			for(int j=0;j<3;++j){
				scanf("%lld",&a[i][j]);
			}
		}

		dp[0][1] = a[0][1];
		dp[0][2] = a[0][1] + a[0][2];
		
		dp[1][0] = a[0][1] + a[1][0];
		dp[1][1] = a[0][1] + a[1][1];
		dp[1][2] = a[0][1] + a[1][2];

		for(int i=2;i<n;++i){
			dp[i][0] = min(dp[i-1][0],dp[i-1][1])+a[i][0];
			
			dp[i][1] = min(min(dp[i][0],dp[i-1][0]),min(dp[i-1][1],dp[i-1][2]))+a[i][1];
			
			dp[i][2] = min(dp[i-1][1],min(dp[i][1],dp[i-1][2]))+a[i][2];
		}
        printf("%d. %lld\n",++test,dp[n-1][1]);
	}
	return 0;
}

koosaga 7년 전 0

기본 알고리즘은 맞는데, 음수가 들어오면 틀릴 거 같네요.

그나저나 1번 행에 대한 하드코딩은 왜 하신건가요? ㅠㅠ

ainch96 7년 전 0

혹시 몰라서 전처리 따로 해야 하나 하면서 계속 고쳐본 결과 입니다.. 아하하....

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

문제

문제

출처

ICPC

알고리즘이 틀린 건가요?

ainch96 7년 전 0

koosaga 7년 전 0

ainch96 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말