글 읽기 - 반례를 도저히 못찾겠습니다

yoohoo030 2년 전 0

top-down 방식으로 풀어봤습니다. 질문게시판의 반례들을 적용해 보았는데도 어디가 틀린건지 모르겠습니다.

컴파일러에서 버퍼 오버런이 난다고 하는데 모듈러 연산도 매번 해줘서 딱히 오버플로우가 날 것 같은 곳이 없는데 왜 계속 뜨는지 모르겠어요 ㅠㅠ

#include <iostream>
using namespace std;
long long mod = 1000000000LL;
long long d[201][201] = { 0 };
long long go(int, int);
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; int k; cin >> n; cin >> k;
	cout << go(n, k);
	return 0;
}
long long go(int n, int k) {
	for (int i = 1; i <= n; i++)
		d[i][1] = 1LL;
	if (d[n][k])
		return d[n][k];
	for (int i = 0; i <= n; i++) {
		d[n][k] += go(n - i, k - 1)%mod;
	}
	d[n][k] = d[n][k] % mod;
	return d[n][k];
}

jinhan814 2년 전 1

15, 16번째 줄에서 k=1일 땐 1을 반환하도록 처리하셨는데, i = 0인 경우가 고려되지 않아서 go(0, 1)이 호출됐을 때 go(0, 1) -> go(0, 0) -> go(0, -1) -> ...에서 런타임에러가 나게 됩니다.

15번째 줄을 i = 0부터 시작하도록 고치셔도 되고(http://boj.kr/e47ec3e0cca94ab6...), k = 1이라면 바로 1을 리턴하도록 고치셔도 됩니다(http://boj.kr/ac68700559784665...).

yoohoo030 2년 전 1

정말 감사합니다!!

i=0인 경우도 호출될 수 있다는걸 미처 생각하지 못했네요. 덕분에 해결했습니다 정말 감사합니다 :)

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

문제

문제

출처

ICPC

반례를 도저히 못찾겠습니다

yoohoo030 2년 전 0

jinhan814 2년 전 1

yoohoo030 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말