글 읽기 - [C++] dp배열의 크기가 dp[1000][1000]인데, 왜 오류가 안 날까요

leejs1030 2년 전 1

dp[1000][1000]이고, 제가 짠 함수에서는 comb(n, r)에서 dp[n][r]의 값을 반환하도록 물었습니다.

그런데, 만약에 comb(1000, 3)과 같은형태로 요청하게 된다면, dp는 0~999까지 있고, 1000번째는 없으므로 오류가 나야하는 것이 아닌가요?

주석에도 작성하였습니다.

이미 구하지 않은 값이라면, 위해서 값을 구한 다음 (36, 37, 38, 39번째 줄) mod 연산 후 arr[n][r]에 저장하고 arr[n][r]의 값을 반환합니다.

그런데, arr[1000][0], arr[1000][100] 등은 잘못된 접근일 것입니다. 왜 오류가 나지 않을까요?

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>



using namespace std;



#define TRUE 1
#define FALSE 0
#define INF 987654321
#define MAX(x, y) x > y ? x : y
#define MIN(x, y) x < y ? x : y
#define all(x) (x).begin(), (x).end()
#define fio() ios_base::sync_with_stdio(0);cin.tie(0)
#define endl '\n'
#define ends ' '
#define ll long long
using namespace std;

int N, K;
int arr[1000][1000]; //dp배열의 크기

int comb(int n, int r);

int main() {
	fio();
	cin >> N >> K; //입력부분
	cout << comb(N, K); //함수 리턴값 출력
}

int comb(int n, int r) {
	int ret = 0;
	if (arr[n][r]) return arr[n][r]; //이미 구한 값이라면 arr[n][r]을 리턴
	else if (n < 0 || r > n || r < 0) ret = 0;
	else if (r == 0 || r == n) ret = 1;
	else if (r == 1 || r == n - 1) ret = n;
	else ret = comb(n - 1, r - 1) + comb(n - 1, r);
    //이미 구하지 않은 값이라면, 위해서 값을 구한 다음 (36, 37, 38, 39번째 줄)
	arr[n][r] = ret % 10007; //mod 연산 후 arr[n][r]에 저장하고
	return arr[n][r]; //arr[n][r]의 값을 반환합니다
    //그런데, arr[1000][0], arr[1000][100] 등은 잘못된 접근일 것입니다. 왜 오류가 나지 않을까요?
}

lukek1101 2년 전 0

왜 arr[1000][0] 이나 arr[1000][100]이 잘못된 접근이죠..?

각각 1000combination 0 = 1 과 1000combination 100 = ~~

이렇게 어떤 값을 가지고 있지 않을까요?

다만 에러가 날 수 있어보이는 곳이 있네요;;

배열은 0부터 시작하는데 문제 조건은 N=1000 까지니까 배열 크기를 1000, 1000 보다 약간씩 더 키워보세요 ㅎㅎ

leejs1030 2년 전 0

@lukek1101

"arr[1000][0] 이나 arr[1000][100]이 잘못된 접근"이라고 말한 이유가 접근 자체가 잘못되었다는 것이 아니라

제 코드 상에서 접근을 하면 오류가 나야한다고 생각한 것(런타임에러, Out of bound)입니다. 말씀해주신

다만 에러가 날 수 있어보이는 곳이 있네요;;

배열은 0부터 시작하는데 문제 조건은 N=1000 까지니까 배열 크기를 1000, 1000 보다 약간씩 더 키워보세요 ㅎㅎ

대로, 원래는 배열의 크기를 약간 더 크게 잡아야하지만, 크게 잡지 않았음에도 런타임 에러가 나지 않는 이유를 묻는 것입니다.

- 이후 추가로 코드를 수정해보니, arr의 크기를 1000 * 900 으로 잡아도 통과(https://www.acmicpc.net/source...)합니다.

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

문제

문제

출처

ICPC

[C++] dp배열의 크기가 dp[1000][1000]인데, 왜 오류가 안 날까요

leejs1030 2년 전 1

lukek1101 2년 전 0

leejs1030 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말