글 읽기 - 어디가 문제인지 모르겠어요..ㅠㅠ

aqws11 8년 전 0

set 배열에 0-9가 등장하는 횟수를 저장해서 이를 더하는 방식으로 구현했는데요.

	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1

...

이런식으로 구하고 마지막에 해당행의 숫자를 모두 더해서 계단수를 구합니다.

그런데 틀렸다고 나와서 알고리즘 자체가 문제인건지 간과한 부분이 있는건지 모르겠어서 질문드립니다 ㅜㅜ

어디가 문제인가요?

#include <stdio.h>

int main(){
	int set[100][10] = { 0 };
	int i, j;
	int n;

	scanf("%d", &n);

	long long res = 0;

	for (i = 0; i < 10; i++){
		if (i == 0)
			set[0][0] = 0;
		else
			set[0][i] = 1;
	}
	
	for (i = 1; i < n; i++){
		for (j = 0; j < 10; j++){
			if (j == 0){
				set[i][j] = set[i - 1][j + 1];
			}
			else if (j == 9){
				set[i][j] = set[i - 1][j - 1];
			}
			else{
				set[i][j] = set[i-1][j+1]+ set[i - 1][j - 1];
			}
		}
	}
	
	for (i = 0; i < 10; i++){
		res += set[n - 1][i];
	}

	printf("%lld", res % 1000000000);
	return 0;
}

baekjoon 8년 전 1

정답이 int 범위를 넘어갈 수 있기 때문입니다.

출력할 때 %연산을 사용하지 말고 중간 중간에 답을 구할 때 %를 사용해주세요.

https://www.acmicpc.net/problem/10430 를 먼저 풀어보는 것이 좋을 것 같아요.

yukariko 8년 전 1

더하는 도중에 int형 범위를 초과하여 오버플로우가 발생할 수 있습니다.

더하는 중간에도 나머지 연산을 수행해야 합니다.

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

문제

문제

출처

ICPC

어디가 문제인지 모르겠어요..ㅠㅠ

aqws11 8년 전 0

baekjoon 8년 전 1

yukariko 8년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말