글 읽기 - 왜 틀렸는지 모르겠습니다...반례가 있다면 알려주시면 감사하겠습니다.

npole0103 3년 전 0

정답도 잘 나오고 하는데 제출하면 틀렸다고 합니다.

혹시 반례가 있나요!? 도저히 모르겠어서 질문 올립니다..

#include <iostream>
using namespace std;

int main()
{
	int len;
	long long mod = 1000000000;
	long long dp[101][10] = {0, };
	long long result = 0;
	
	cin >> len;
	
	//dp에는 방법의 가지 수가 저장됨.
	//dp[digit number][last digit]
	//digit number >> 몇 자리 숫자인가
	//last digit >> 끝의 자리 숫자에 대한 가지 수
	//점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
	
	// 1~9까지 예외처리
	for(int i = 1 ; i < 10 ; i++)
		dp[1][i] = 1;
	
	dp[1][0] = 0;
	
	for(int i = 2 ; i <= len ; i++)
	{
		for(int j = 0 ; j < 10 ; j++)
		{
			if(j == 0)
				dp[i][j] = dp[i - 1][j + 1] % mod;
			else if(j == 9)
				dp[i][j] = dp[i - 1][j - 1] % mod;
			else
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
		}
	}
	
	for(int i = 0 ; i < 10 ; i++)
		result += dp[len][i];
	
	cout << result << endl;
	
	return 0;
}

swdaniel 3년 전 1

result % mod 를 추가 해야 할거 같습니다

npole0103 3년 전 0

swdniel님 우선 해결은 됐습니다. 정말 감사드립니다. 이렇게 보니 정말 허탈하네요.

하지만 제가 아직 많이 부족해서 결과값도 mod 처리를 하는 정확한 이유를 알지 못합니다.

이미 for문 계산 과정에서 mod 처리를 다 해줬는데 결과값도 mod로 처리하는 이유가 있을까요!?

덧글 보신다면 설명 한번 부탁드립니다.

swdaniel 3년 전 2

38번째 for 문에서 dp[len][i]는 mod보다 작은 값들이지만, 그런 값들을 result에다가 10번을 더하면 result 가 mod 보다 커질 수 있습니다

문제에서는 정답을 mod 로 나눈 나머지를 묻고 있고 아까 말했듯이 result가 mod보다 클 수 있기 때문에 한 번 더 mod 처리를 해줘야합니다

예) 100,000,000 이 10개 있으면 result 가 1,000,000,000 이 되지만, 저희가 출력해야 할 것은 0입니다

npole0103 3년 전 0

너무 확실하게 설명해주셔서 의문점 하나 없이 바로 이해했습니다.

아직 갈 길이 먼 것 같습니다. 가르쳐주신 부분 다음 비슷한 문제 만났을 땐 한번에 해결하도록 상기시키고 또 상기시켜야겠습니다.

감사드립니다!!

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다...반례가 있다면 알려주시면 감사하겠습니다.

npole0103 3년 전 0

swdaniel 3년 전 1

npole0103 3년 전 0

swdaniel 3년 전 2

npole0103 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말