글 읽기 - 1309 동물원 / 간단한 dp인데 탑다운 구현이 잘못됬나요?

Green55 6년 전 0

solve(i,j) = 현재 i번째 칸을 배치할 차례고, 이전 배치가 j였을때 앞으로 가능한 경우의 수

나머지 구현은 아직 안했는데 예제도 제대로 아

#include<bits/stdc++.h>
using namespace std;
//before : 이전 배치가  0 - XX, 1 - OX, 2-XO , 3-OO  
int n, dp[100000][4];
int solve(int here, int before){
	if(here == n) return 1;
	int &ret = dp[here][before];
	if(ret!=-1) return ret;
	++here;
	ret = solve(here,0);
	if(before == 0 || before == 2)
		ret+= solve(here,1);
	if(before == 0 || before == 1)
		ret+= solve(here,2);
	if(before == 0)
		ret += solve(here,3);
	return ret;
	
}
int main(){
	scanf("%d",&n);
	memset(dp,-1,sizeof(dp));
	printf("%d", solve(0,0));
}

Green55 6년 전 0

가로로도 못붙네요

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

문제

문제

출처

ICPC

1309 동물원 / 간단한 dp인데 탑다운 구현이 잘못됬나요?

Green55 6년 전 0

Green55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말