글 읽기 - 31% 반례부탁드립니다.

dhtmdgus2134 3년 전 0

게시판에 있는 모든 반례들은 다 찾아봤는데 제가 뭘 놓치고 있는지 도움좀 부탁드립니다.

직관적으로 풀었는데 31퍼에서 막히네요...

#include<iostream>
#define MAX 1001


using namespace std;

int arr[MAX];
int DP[MAX];
int n;
int max(int a, int b) {
	return a > b ? a : b;
}

int main(void) {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i <= n; i++) {
		DP[i] = max(DP[i], DP[i - 1] + arr[1]);
		if (arr[i] >= DP[i]) { // 현제 DP보다 arr에 담겨 있는 수가 크다면 
			int a = n / i;    //DP의 배수들은 최댓 값을 가지도록 초기화
			int b = n % i;
			for (int j = 1; j <= a; j++) {
				DP[j*i] = arr[i] * j;
				DP[n] = max(DP[n], DP[j*i] + DP[n - j * i]); 
			}//배수로 곱해 나가며 n까지 남는 수들은 각 DP와 더하여 최댓값 비교
		}    //1 -> n 까지 가면서 DP에 담기는 값들은 모두 최댓값을 가지도록 함
	}
	cout << DP[n];
}

yj10516 3년 전 3

1 5 6 1 1 1

Ans: 15

dhtmdgus2134 3년 전 0

반례 정말 감사합니다.

반례를 반영하여 25번 라인을

DP[j*i] = max(DP[j*i] , arr[i] * j);

으로 수정했는데도 31퍼에서 막히네요... ㅠ

yj10516 3년 전 6

반례

12
1 1 6 8 11 1 1 1 1 1 1 1

Ans: 25

dhtmdgus2134 3년 전 0

yj10516님 또 신경써주셔서 정말 감사합니다.

마지막으로 말씀해주신 부분에서 코드를 완전히 갈아 엎어야 겠다는 생각이 들었네요...

방문하는 DP에서 가장 최댓값을 유지하고 있어야 하는데 제가 작성한 코드에서는 이전에 방문한 DP에서 최댓값을 가질 수 밖에 없게 만들었다고 생각했는데

작성 해주신 반례에서 잘못되었다는 것을 느꼇네요...

방문하는 DP에서 이전 카드팩의 케이스들을 체크하여 최댓값을 가지게 하는 점화식을 세우는 방법으로 풀어보도록 하겠습니다!

그리고 혹시 가능하다면 반례를 찾아내는 쉬운 방법이 있을까요 ?

한가지 방법으로 생각이 굳혀지면 도저히 반례를 찾아내기 힘들네요..

팁 부탁드립니다!

yj10516 3년 전 4

어떻게 반례를 쉽게 찾을수 있을지... 저도 잘 모르겠습니다...

위 코드에서는 어디서 틀릴 수 있을까를 생각해 봤었는데

25번째줄에서 최댓값을 덮어씌우지 않을까 -> 첫번째 반례

25번째 줄을 맞게 고쳤다면 26번째 줄도 틀렸나? -> DP[j*i] + DP[n - j * i] 에서 DP[n - j*i] 에 카드팩을 다른 여러개를 사는 경우를 고려하는가?

-> 카드팩 서로 다른 3개를 사용해야하는 반례

왜 맞아야 하는지 생각해보는것도 좋을것 같습니다. 잘못된 답을 출력하므로 어디선가 내가 생각했던 논리가 틀렸을 것인데,

DP[i] = i를 사는 최대비용이 저장될 것이다라고 가정하고 생각해봤을때

26번째줄과 20번째 줄만 DP[i]에 값을 저장하고 여기에서

i<n의 경우 DP[i] = arr[i]*ai + arr[1]*a1 형태가 됨으로

DP[n] 이 최대 서로다른 카드팩 2개와 카드팩 1만 사는 경우를 고려해서 틀렸음을 알 수 있습니다.

dhtmdgus2134 3년 전 3

왜 맞아야 하느냐 생각해보는게 중요해보이네요..

저도 다른 사람들 코드 보면서 시각을 키우는 연습을 해나가야겠네요

끝까지 신경써주셔서 감사합니다

항상 건강하시고 하는일 번창하세요!

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

문제

문제

출처

ICPC

31% 반례부탁드립니다.

dhtmdgus2134 3년 전 0

yj10516 3년 전 3

dhtmdgus2134 3년 전 0

yj10516 3년 전 6

dhtmdgus2134 3년 전 0

yj10516 3년 전 4

dhtmdgus2134 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말