글 읽기 - 반례가 무엇일까요?

moyoungmin 5년 전 0

예상 되는 반례를 생각했는데도 저가 모르는게 있어요.. 혹시 어떤 반례가 있을까요?

#include <iostream>
using namespace std;

int dp[1000][1000];
int value[1000][1000];

int max(int a, int b, int c) {
	int max = a;
	if (max < b) {
		max = b;
	}
	if (max < c) {
		max = c;
	}
	return max;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> value[i][j];
		}
	}
	dp[0][0] = value[0][0];
	for (int i = 0; i < m; i++) {
		dp[0][i] = dp[0][i - 1] + value[0][i];
	}
	for (int i = 1; i < n; i++) {
		dp[i][0] = dp[i - 1][0] + value[i][0];
	}
	//Initialize

	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + value[i][j];
		}
	}

	cout << dp[n - 1][m - 1] << endl;
}

krenerd 5년 전 1

dp와 value 배열의 크기를 1001x1001로 잡아주시면 A/C 나오네요

krenerd 5년 전 1

N의 범위가 1000일 수도 있기 떄문입니다...

moyoungmin 5년 전 0

감사합니다.

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

문제

문제

출처

ICPC

반례가 무엇일까요?

moyoungmin 5년 전 0

krenerd 5년 전 1

krenerd 5년 전 1

moyoungmin 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말