글 읽기 - 1562번 계단수문제 재귀 DP 질문드립니다.

unilep 6년 전 0

아래와 같이 짜봤는데

일단 정답이 안나오니 틀린 점화식입니다.

어디가 문제인걸까요?

d[i][j][k] 는 i길이의 끝자리수가 j 일때 k는 0~9 의 숫자들이 set되어있는 상태입니다.

#include<iostream>
#include<cstring>
#define MOD 1000000000
using namespace std;
int n, d[101][10][(1 << 10) + 1];

int f(int len, int no, int status){
	if(len < 10) return 0;
	if(status == (1 << 10) - 1) return 1;
	
	int& ret = d[len][no][status];
	if(ret != -1) return ret;
	ret = 0;

	if(no-1 >= 0) 
		ret += f(len-1, no-1, status | (1 << (no-1))) % MOD;
	if(no+1 <= 9) 
		ret += f(len-1, no+1, status | (1 << (no+1))) % MOD;

	return ret;
}

int main(){
	cin >> n;
	if(n < 10){
		cout << 0;
		return 0;
	}
	else if(n == 10){
		cout << 1;
		return 0;
	}
	memset(d, -1, sizeof(d));
	for(int i=0; i<10; i++) f(n, i, 0);
	int ans = 0;
	for(int i=0; i<10; i++) ans += d[n][i][(1 << 10) - 1] % MOD;
	cout << ans % MOD;
	return 0;
}

Green55 6년 전 0

일단 10보다 큰 모든 인풋에 대해 -10이 출력되는거 보면

i=0~9 일때 전부 ans에 -1만 더해지는거 같네요.

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

문제

문제

출처

ICPC

1562번 계단수문제 재귀 DP 질문드립니다.

unilep 6년 전 0

Green55 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말