글 읽기 - 9465번 도움 부탁드립니다.

sbim 6년 전 0

안녕하세요, 복잡하지 않은 문제라고 생각했는데, 틀린 곳을 찾기가 어렵네요;;

매 column마다 위 / 아래 선택 혹은 아무것도 선택하지 않는 세 가지 케이스를 고려하고,

다음 column에 미치는 영향을 status로 해서 재귀로 DP를 짰습니다.

뭘 실수한 걸까요? 도움 부탁드립니다.

#include <iostream>

using namespace std;

int T, N;
int arr[2][100000];
int memo[100001][3];

int solve(int index, int status)
{
	if (index == N+1) return 0;
	int & res = memo[index][status];
	if (res!= -1) return res;

	int case1=0, case2=0, case3=0;
	if (status != 1) case1 = arr[0][index] + solve(index+1, 1);
	if (status != 2) case2 = arr[1][index] + solve(index+1, 2);
	case3 = solve(index+1, 0);

	res = case1 > case2 ? case1 : case2;
	res = res > case3 ? res : case3;

	return res;
}

int main(void)
{
	for(scanf("%d", &T);T--;) {
		scanf("%d", &N);

		for (int i = 0 ; i < N ; i++) scanf("%d", &arr[0][i]);
		for (int i = 0 ; i < N ; i++) scanf("%d", &arr[1][i]);

		for (int i = 0 ; i< N ; i++) for (int j= 0 ; j < 3 ; j++) memo[i][j] = -1;
		int res = solve(0, 0);
		cout<<res<<endl;
	}
    return 0;
}

movie_jo 6년 전 0

if (index == N) return 0;

하시면 될 것 같은데.. 확실하진 않아요

sbim 6년 전 0

헉 0부터 시작해놓고 N+1까지 갔네요 -_-; 감사합니다. 여러번 봤는데 왜 못찾았을까요;;

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

문제

문제

출처

ICPC

9465번 도움 부탁드립니다.

sbim 6년 전 0

movie_jo 6년 전 0

sbim 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말