글 읽기 - DP 쉬운 계단 수 질문이요ㅠㅠ (나머지처리 질문)

youu 6년 전 0

문제 자체는 맞았는데 나누는 부분에 질문이 있어서요!!

sum += (d[n][i]) % 1000000000

printf("%d\n", sum% 1000000000)

이렇게 처리한거나

sum = (sum + d[n][i]) % 1000000000

printf("%d\n", sum% 1000000000);

이렇게 처리한거나 둘이 나오는 답은 같은 거 아닌가요?ㅠㅠㅠ

왜 둘이 왜 다르게 인식되는 건가요ㅜㅜ

sum += (d[n][i]) % 1000000000

printf("%d\n", sum% 1000000000)

이렇게 하면 오답으로 처리되네요ㅠㅠ

----------------질 문 --------------------------------------------
//오답처리 되는 코드
for (int i = 0; i <= 9; i++)
       sum  += (d[n][i]) % 1000000000;
printf("%d\n", sum% 1000000000);


//맞게 처리 되는 코드
for (int i = 0; i <= 9; i++)
         sum = (sum + d[n][i]) % 1000000000;
printf("%d\n", sum% 1000000000);
-----------------------------------------------------------------

////제출해서 답안으로 인정받은 코드.c ////////////////////////////////
#include <stdio.h>
int n,d[101][11], sum;
int main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= 9; i++)
		d[1][i] = 1;

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0)
				d[i][0] = d[i - 1][1] % 1000000000;
			else if (j == 9)
				d[i][9] = d[i - 1][8] % 1000000000;
			else
				d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % 1000000000;
		}
	}
/***********질문한 코드 부분 ***************************/
	for (int i = 0; i <= 9; i++)
		sum = (sum + d[n][i]) % 1000000000;  /// <--- 질문 부분 !!!
	printf("%d\n", sum% 1000000000);
 /***************************************************/
}
////////////////////////////////////////////////////////////////////////

lucidash 6년 전 0

10억 으로 나눈 나머지인데

d[n][0..9] = 9억 인 경우를 생각해보시면 될 것 같습니다.

cubalys 6년 전 1

나머지 연산이 우선순위를 가지기 때문에

(d[n][i]) % 1000000000의 값이 sum에 계속해서 더해지게 되므로 오버플로우가 나는거 같네요

+=을 사용하고 싶으시다면

for (int i = 0; i <= 9; i++)
sum += d[n][i], sum %= 1000000000;

으로 하셔야 할듯

youu 6년 전 0

@cubalys 그러네요 알려주신대로 고치니까 맞게처리됩니다 감사합니다

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

문제

문제

출처

ICPC

DP 쉬운 계단 수 질문이요ㅠㅠ (나머지처리 질문)

youu 6년 전 0

lucidash 6년 전 0

cubalys 6년 전 1

youu 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말