글 읽기 - dp를 이용하여 3가지 경우로 했는데 반례가 있는걸까요??

vhxpffltm 7년 전 0

여러 예시를 넣어서 확인결과 알맞게 나오던데

틀린이유를 모르겠습니다 ㅠㅠ

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<string>
#pragma warning(disable:4996)
using namespace std;

int main()
{
	int dp[10010] = { 0 }, N, arr[10010] = { 0 };
	cin >> N;
	for (int i = 1; i <= N; i++)
		scanf("%d", &arr[i]);
	for (int i = 1; i <= N; i++) {
		dp[i] = max(dp[i - 1], max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
	}
	cout << dp[N];
	return 0;
}

cozyyg 7년 전 2

1000

900

800

700

답은 1000,900,800,700 마셔서 3000인데 저 코드로는 2402가 나오네요.

vhxpffltm 7년 전 0

ㅜ.ㅜ 1000+900+800+700 해서 전 3400이 제대로 나오는데 코드 자체에 문제가 있는걸까여?? 캡처.JPG

cozyyg 7년 전 0

아아 3400이 맞네요 역시 산수는 어렵습니다...

index 문제일 가능성이 높은데 dp[-1]이나 dp[-2] 같은게 안 나오게 잘 수정하면 될 것 같습니다.

초기화 적절히 하니까 되는 것 같네요

vhxpffltm 7년 전 0

dp배열의 음수값 문제였네요 해결했ㅅ습니다

정말 감사합니다~~~

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

문제

문제

출처

ICPC

dp를 이용하여 3가지 경우로 했는데 반례가 있는걸까요??

vhxpffltm 7년 전 0

cozyyg 7년 전 2

vhxpffltm 7년 전 0

cozyyg 7년 전 0

vhxpffltm 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말