글 읽기 - 왜 코드가 맞는지 모르겠습니다.

papayetoo 4년 전 0

분명 문제에서 N 자릿수의 계단수 구할 때 첫 자리가 0으로 시작하는 것이 없다고 하여.

아래 코드에서 주석으로 문제되는 부분이라 체크한 곳에서 i = 1부터 더하는 것이 맞다고 생각했는데 틀렸다고 해서

i = 0부터 바꾸니 옳은 코드로 나오는데 제 생각이 잘못된 건지 궁금합니다.

#include <iostream>

using namespace std;

long long solution(int n);

int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	cout << solution(n);
	
	return 0;
}


long long solution(int n) {

	long long ret = 0;
	const long long mod = 1000000000;

	long long dp[101][10];
	dp[1][0] = 0;

	for (int i = 1; i <= 9; i++) {
		dp[1][i] = 1;
	}

	if (n == 1)
		return 9;

	for (int j = 2; j <= n; j++) {

		for (int k = 0; k <= 9; k++) {
			if (k == 0) dp[j][k] = dp[j - 1][1] % mod;
			else if (k == 1) dp[j][k] = (dp[j - 1][2] + dp[j-1][0]) % mod;
			else if (k == 9) {
				dp[j][k] = (dp[j - 1][8]) % mod;
			}
			else {
				dp[j][k] = (dp[j - 1][k - 1] + dp[j - 1][k + 1]) % mod;
			}
		}
	}

	for (int i = 0; i < 10; i++) {
        //문제가 되는 부분
        // i = 1부터 시작해야 되지 않는지?
		ret = (ret + dp[n][i]) % mod;
	}

	return ret % mod;
}

3587jjh 4년 전 0

i=1부터 시작해야 된다는거면, dp[n][k] = "n자리이면서 k로 시작하는 계단수의 개수"로 정의하신건가요?

그러면 35째줄은 의미가 맞지 않습니다. 그렇다고 dp[n][k] = "n자리이면서 k로 끝나는 계단수의 개수"라고 하면

i=1부터 시작해야된다는 말이 이상합니다. 두 정의가 혼용되고 있는데 의도치 않게 답이 나온것으로 보입니다.

papayetoo 4년 전 0

dp[n][k] 는 'n 자리수이면서 k로 시작하는 계단 수'로 정의한 게 맞습니다.

35번 째줄의 의미는 3자리수 이면서 1로 시작하는 계단수를 구하는 것을 예로 들어 설명하면,

처음 1 이후에 올 수 있는 수는 2자리수이면서 시작수가 0 또는 2가 있을 때처럼 편하게 구하기 위해서 설정한 것입니다.

하지만 sum 계산시에는 dp[n][0]는 제외되어야 한다고 생각한 것 뿐입니다. 제 생각에는 두 정의는 전혀 혼용되지 않습니다.

3587jjh 4년 전 0

그러면 23째줄 값도 1로 해야될것같네요

3587jjh 4년 전 0

n 자리수이면서 k로 시작하는 계단 수라는 정의에서 제가 무의식적으로 맨 앞자리가 0으로 시작하는 경우는 제외했을거라고 오해했네요

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

문제

문제

출처

ICPC

왜 코드가 맞는지 모르겠습니다.

papayetoo 4년 전 0

3587jjh 4년 전 0

papayetoo 4년 전 0

3587jjh 4년 전 0

3587jjh 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말