글 읽기 - 2342번 DDR 문제 질문합니다

showx123 7년 전 0

DP를 이용하여 풀었습니다.

시간초과가 안나고 오답이 계속 나오는데

어디서 오류가 나는지 모르겠습니다...

계속해서 찾아보고 테스트 넣어보는데 잘 안찾아지네요..

오류나는 케이스나 문제 있는 코드 부분 알려주세요ㅠㅠ

#include <stdio.h>
#define min(X,Y) ((X) < (Y) ? (X) : (Y))

//https://www.acmicpc.net/problem/2342


int arr[100005];
int DP[100005][6][6];
int len; //length of input array without '0'



//return its energy value start from 'cur'
//l : left foot, r : right foot, cur : current position in the array
int recur(int l, int r, int cur){
\	//end of array
	if (cur == len + 1)
		return 0;

	//check DP table
	if (DP[cur][l][r] != 0)
		return DP[cur][l][r];

	//don't need to move
	if (arr[cur] == l || arr[cur] == r){
		DP[cur][l][r] = recur(l, r, cur + 1) + 1;
		return DP[cur][l][r];
	}

	//at start position
	if (l == 0 || r == 0){
		if (l == 0 && r == 0)
			return recur(l, arr[cur], cur + 1) + 2;

		if (l == 0){
			if (((arr[cur] - r) == 2) || ((r - arr[cur]) == 2))
				return min((recur(arr[cur], r, cur + 1) + 2), (recur(l, arr[cur], cur + 1) + 4));
			else
				return min((recur(arr[cur], r, cur + 1) + 2), (recur(l, arr[cur], cur + 1) + 3));
		}
		else{
			if (((arr[cur] - l) == 2) || ((l - arr[cur]) == 2))
				return min((recur(arr[cur], r, cur + 1) + 4), (recur(l, arr[cur], cur + 1) + 2));
			else
				return min((recur(arr[cur], r, cur + 1) + 3), (recur(l, arr[cur], cur + 1) + 2));
		}
	}

	//current foots are face each other => 2 cases
	if (((l - r) == 2) || ((r - l) == 2)){
		DP[cur][l][r] = min(recur(arr[cur], r, cur + 1), recur(l, arr[cur], cur + 1)) + 3;
		return DP[cur][l][r];
	}
	else{ //foots are not face each other => 1 case? 2 cases?
		if (((arr[cur] - l)) == 2 || ((l - arr[cur])) == 2){
			DP[cur][l][r] = min((recur(l, arr[cur], cur + 1) + 3), (recur(arr[r],r,cur+1) + 4));
			return DP[cur][l][r];
		}
		else{
			DP[cur][l][r] = min((recur(arr[cur], r, cur + 1) + 3), (recur(l,arr[cur],cur+1) + 4));
			return DP[cur][l][r];
		}
	}
}

int main(void){
	int i;

	for (i = 1; 1; i++){
		scanf("%d", &arr[i]);

		if (arr[i] == 0){
			len = i - 1;
			break;
		}
	}

	printf("%d\n", recur(0, 0, 1));

}

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

문제

문제

출처

ICPC

2342번 DDR 문제 질문합니다

showx123 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말