글 읽기 - 예제, 질문게시판 반례 다 적용해봤는데요.. 틀리는 이유

apdh25 4년 전 1

고수님들께서 한번만 봐주시면 감사드리겠습니다.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pair;

int main()
{
	Pair dp[16];
	Pair arr[16];
	int n;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
	{
		int time, price;
		scanf("%d %d", &time, &price);
		arr[i].first = time;
		arr[i].second = price;
		dp[i].first = arr[i].first;
		dp[i].second = arr[i].second;
	}

	for (int i = n; i >= 1; i--)
	{
		// dp 코드작성 
		if (i + arr[i].first - 1 > n) {
			dp[i].second = 0;
			continue;
		}

		int MAX = -987654321;

		for (int j = i + arr[i].first; j <= n; j++) {
			MAX = max(MAX, dp[j].second);
		}

		if (MAX > 0)
			dp[i].second += MAX;
	}

	printf("%d\n", dp[1].second);
	return 0;
}

djm03178 4년 전 3

dp[1].second가 무조건 답일까요?

2
5 1
1 1

apdh25 4년 전 1

예리한 반례 진심으로 감사드립니다ㅠㅠ

for문이 끝난 뒤 dp를 살펴보니 무조건 dp[1]에 있는값이 답이 아니더군요.

제 부족한 질문에 답변달아주셔서 다시한번 진심으로 감사드리고 앞으로 더 열심히 하겠습니다!!

좋은하루되세요^_^

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

문제

문제

출처

ICPC

예제, 질문게시판 반례 다 적용해봤는데요.. 틀리는 이유

apdh25 4년 전 1

djm03178 4년 전 3

apdh25 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말