글 읽기 - 틀렸는데.. 코드 리뷰 좀 부탁드립니다

seongkwonii 4년 전 0

5 100
10 10000
50 50
40 100
10 90
9 101

10291이 나와야 하는데 10241이 나오네요...

근데 코드 어디가 틀린지 모르겠네요...

#include <iostream>
using namespace std;

/*
	DP[] 는 i번째부터 시작해서 최대값이 되는 애.
*/
int dp[100], w[110], v[110]; // n is 100
int n, k, ans;

int f(int cur, int weight){

	if( cur == n ){
		return 0;
	}
	int& ret = dp[cur];
	if(ret)
		return ret;

	// ret = 0;
	if( weight + w[cur] <= k)
		ret = v[cur] + f(cur+1, weight + w[cur]);
	// 만약 위에 if문을 거친 경우 ret에 있는 값과 비교하기 위해서
	// 현재것을 선택하지 않고, 다음것을 선택하는 경우
	ret = max(ret, f(cur+1, weight));
	ans = max(ans, ret);
	return ans;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; ++i){
		cin >> w[i] >> v[i];
	}
	cout << f(0,0) << endl;
	return 0;
}

seongkwonii 4년 전 0

line 16, 17을 지워봤는데.. 시간초과가 아니라 틀렸습니다가 나오네요....;;;;;

#include <iostream>
using namespace std;

/*
	DP[] 는 i번째부터 시작해서 최대값이 되는 애.
*/
int dp[100], w[110], v[110]; // n is 100
int n, k, ans;

int f(int cur, int weight){

	if( cur == n ){
		return 0;
	}
	int& ret = dp[cur];
	// if(ret)
	// 	return ret;

	// ret = 0;
	if( weight + w[cur] <= k)
		ret = v[cur] + f(cur+1, weight + w[cur]);
	// 만약 위에 if문을 거친 경우 ret에 있는 값과 비교하기 위해서
	// 현재것을 선택하지 않고, 다음것을 선택하는 경우
	ret = max(ret, f(cur+1, weight));

	ans = max(ans, ret);
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; ++i){
		cin >> w[i] >> v[i];
	}
	cout << f(0,0) << endl;
	return 0;
}

sait2000 4년 전 1

각각 위에 거 아래 거 반례입니다. 지금 코드를 dp하려고 하면 cur와 weight가 모두 일치할 때만 예전에 계산한 값을 사용할 수 있습니다. weight를 적어두지 않으면 전에 계산했던 때보다 더 많이/적게 담을 수 있는데도 예전 결과를 쓰기 때문에 틀립니다.

seongkwonii 4년 전 0

weight를 적어두지 않으면.. 이라는게 무슨 말인지 잘 모르겠습니다

코드는 다시 이걸로 하고 있는데요

말씀하신 반례가

4 100

10 100

50 5

40 90

9 2000

에서 나오는거 같아요

하나하나 출력하면서 보고 있긴한데.. 어렵네요 ㅠㅠ

#include <iostream>
using namespace std;

/*
	DP[] 는 i번째부터 시작해서 최대값이 되는 애.
*/
int dp[100], w[110], v[110]; // n is 100
int n, k, ans;

int f(int cur, int weight){

	if( cur == n ){
		return 0;
	}
	int& ret = dp[cur];
	if(ret)
		return ret;

	// ret = 0;
	if( weight + w[cur] <= k)
		ret = v[cur] + f(cur+1, weight + w[cur]);
	// 만약 위에 if문을 거친 경우 ret에 있는 값과 비교하기 위해서
	// 현재것을 선택하지 않고, 다음것을 선택하는 경우
	ret = max(ret, f(cur+1, weight));

	ans = max(ans, ret);
	// cout << "cur " << cur << " ret " << ret << " weight " << weight << " v[cur] " << v[cur] << endl;
	return ret;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for(int i=0; i<n; ++i){
		cin >> w[i] >> v[i];
	}
	cout << f(0,0) << endl;
	return 0;
}

sait2000 4년 전 1

f가 같은 cur값으로 호출돼도 weight값이 다르면 논리적으로 계산결과가 다를 수 있는데 전에 cur만 똑같았을 때의 값을 사용하니까 틀립니다. 아예 dp를 이차원 배열이나 map을 활용해서 cur과 weight이 둘 다 같을 때만 전에 계산한 결과를 사용해야 올바른 답이 나옵니다.

...그리고 그렇게 해서 시간 초과가 나면, 원래 이렇게 푸는 문제가 아니어서 그렇습니다.

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

문제

문제

출처

ICPC

틀렸는데.. 코드 리뷰 좀 부탁드립니다

seongkwonii 4년 전 0

seongkwonii 4년 전 0

sait2000 4년 전 1

seongkwonii 4년 전 0

sait2000 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말