글 읽기 - 어디가 틀린건가요??

asterisk120 5년 전 0

일단 알고리즘은

n이 2일때

10 12, 20, 22 , .... 이고

n이 3일때

101,120,123 , 210,212,232,234, ...

이렇게 되서 n=i일때 가장 상위 자릿수와 n이 i-1일때의 계단수중 차이가 1인 것들의 합이 n=i의 계단수를 이룬다는걸 깨닫고 점화식으로 만들었습니다

그리고 0으로 시작하는 수는 없지만 10이나 101같은걸 처리하기위해서 모든 자릿수의 0엔 1을 채워주었으며 마지막에 출력시 결과값에서 -1을 해주었습니다

memo[A][B]에서 A는 자릿수, B는 0부터 9까지 계단수의 개수입니다 (예를들어 memo[5][1]=은 5자리의 계단수중 1로 시작하는 계단수들의 수입니다)

그리고 점화식에서 더해갈시에 오버플로우를 막기위해 문제에서 나왔던 10억나누기를 해주었습니다

이렇게해서 결국 틀렸는데

점화식이 잘못된걸까요?? 어디가 틀린건가요??

#include <iostream>
#include <vector>
constexpr int MAX = 101;

int memo[MAX][10];

int main(void)
{
	int n, quantity = 0;

	scanf("%d", &n);
	std::fill(memo[1], memo[1] + 10, 1);
	for (int i = 1; i <= n; i++)
		memo[i][0] = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= 9; j++) {
			if (j + 1 > 9)
				memo[i + 1][j] = memo[i][j - 1];
			else
				memo[i + 1][j] = (memo[i][j - 1] + memo[i][j + 1])%1000000000;
		}
	}
	for (int i = 0; i <= 9; i++)
		quantity += memo[n][i];

	printf("%d", (quantity - 1)%1000000000);
}

asterisk120 5년 전 0

아 그리고 아래 for문 부분도 %10억 해줬는데 안됩니다..

	for (int i = 0; i <= 9; i++)
		quantity += memo[n][i];

jh05013 5년 전 2

for문 부분을 %10억 하셨으면 그 코드를 그대로 올려 주세요. quantity+= memo[n][i]%10억을 하셨다는 뜻인지, quantity = (quantity+memo[n][i])%10억을 하셨다는 뜻인지 불분명합니다.

asterisk120 5년 전 0

아 죄송합니다;; 말을 명확하게 안했네요

재귀빠져나온후 처음 퀀티티는 10억으로 이미 나눠진 후라 메모를 더하고 10억으로 나누는 식으로 했습니다

for (int i = 0; i <= 9; i++) {
	quantity += memo[n][i];
    quantity %= 1000000000;
}

jh05013 5년 전 1

우선 4를 넣으면 61이 나와야 합니다.

설명의 "n=2일 때 10 12, 20, 22" 부터 무슨 뜻인지 잘 모르겠습니다. 20은 계단수가 아닙니다.

asterisk120 5년 전 0

아;; 잘못적었네요 21 23이라고 적어야하는데... 피곤해서 그만... 죄송합니다

n=4일때 1010 1012 1210 1211 1232 1234인데 디버깅해보니 개수가 5개만 나오네요.. 이게 반례인듯합니다

답변해주셔서 감사합니다!!

asterisk120 5년 전 0

아 1211은 아니구나;; 쨌든 감사합니다 n=4 처음부터 세보겠습니다

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

문제

문제

출처

ICPC

어디가 틀린건가요??

asterisk120 5년 전 0

asterisk120 5년 전 0

jh05013 5년 전 2

asterisk120 5년 전 0

jh05013 5년 전 1

asterisk120 5년 전 0

asterisk120 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말