글 읽기 - 테스트케이스는 잘 들어가는데 틀렸다고 나오네요

kangsy763 4년 전 0

무엇이 문제인걸까요? 테스트 케이스는 잘 나옵니다

#include <stdio.h>
using namespace std;

int main() {
	long long dp[101][10] = { 0 };
	int n,sum=0;
	scanf("%d", &n);
	for (int i = 1; i < 10; i++) {
		dp[1][i] = 1;
		if (i == 9) {
			dp[2][i] = 1;
		}
		else {
			dp[2][i] = 2;
		}
	}
	for (int i = 3; i < 101; i++) {
		for (int j = 1; j < 10; j++) {
			if (j == 1) {
				dp[i][j] = (dp[i - 2][j] + dp[i - 1][j + 1])% 1000000000;
			}
			else if (j == 9) {
				dp[i][j] = (dp[i - 1][j - 1])% 1000000000;
			}
			else {
				dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])% 1000000000;
			}
		}
	}
	for (int i = 1; i < 10; i++) {
		sum += dp[n][i]% 1000000000;
	}
	printf("%d", sum%1000000000);
	return 0;
}

nahwasa 4년 전 0

long long 임에도 오버플로우가 납니다.

+보다 % 연산자가 먼저 불립니다.

kangsy763 4년 전 0

답변이 이해가 잘 안됩니다... ㅜ

nahwasa 4년 전 1

sum += dp[n][i]% 1000000000;

요건 sum = sum + dp[n][i]% 1000000000;

이렇게 작동합니다.

즉 dp[n][i]% 1000000000; 이후에 sum에 더해지게되서, sum은 계속해서 증가하게 됩니다.

그래서 long long의 범위를 넘어가게되서 오버플로우가 나게됩니다.

결론적으로 예를들어 입력으로 100을 넣으시면

-276563184

이런 값이 뜨게됩니다.

sum += dp[n][i];
sum %= 1000000000;
혹은
sum = (sum + dp[n][i]) % 1000000000;
와 같이 하셔야 합니다.

kangsy763 4년 전 1

아!!!!!!!! 마지막에 sum에 하는 것은 저래서 의미가 없는거군요 정말 감사합니다!!

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

문제

문제

출처

ICPC

테스트케이스는 잘 들어가는데 틀렸다고 나오네요

kangsy763 4년 전 0

nahwasa 4년 전 0

kangsy763 4년 전 0

nahwasa 4년 전 1

kangsy763 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말