글 읽기 - 밑의 두 함수의 차이를 잘 모르겠습니다

hojinseo 5년 전 0

아래 코드 내 함수 solution 1이 solution 2와는 다르게 왜 런타임 에러가 나는지 모르겠습니다.

그리고 질문이 하나 더 있는데

cache 배열을 MAX값으로 초기화 시킨 후, solution3처럼 수행시키면 왜 수행시간이 오래 걸리는지 잘 모르겠습니다ㅠㅠ

int solution(vector<int>& coins, int cnt, int cursum) {
	if (cursum > K_2294) {
		return MAX;
	}
	if (cursum == K_2294) {
		return 0;
	}
	 
	if (cache_2294[cnt][cursum] != -1) {
		return cache_2294[cnt][cursum];
	}
	cache_2294[cnt][cursum] = MAX;
	for (int i = 0; i < N_2294; ++i) {
		//int& pickCoin = coins[i];
		//if (canPick(cursum, pickCoin)) 
		{
			//debug.push(pickCoin);
			cache_2294[cnt][cursum] = min(cache_2294[cnt][cursum], solution(coins, cnt + 1, cursum + coins[i]) + 1);
			//debug.pop();
		}
	}
	return cache_2294[cnt][cursum];
}

int solution2(vector<int>& coins, int n, int cursum) {
	if (cursum > K_2294) {
		return MAX;
	}
	if (n == N_2294) {
		if (cursum == K_2294) {
			return 0;
		}
		return MAX;
	}
	
	if (cache_2294[n][cursum] != -1) {
		return cache_2294[n][cursum];
	}
	cache_2294[n][cursum] = min(solution2(coins, n + 1, cursum), solution2(coins, n, cursum + coins[n]) + 1);
	/*for (int i = 0; i < coins.size(); ++i) {
		int& pickCoin = coins[i];
		cache_2294[cnt][cursum] = min(cache_2294[cnt][cursum], solution(coins, cnt + 1, cursum + pickCoin));
		
	}*/
	return cache_2294[n][cursum];
}

int solution3(vector<int>& coins, int cnt, int cursum) {
	if (cursum == K_2294) {
		return cnt;
	}

	if (cache_2294[cnt][cursum] != MAX) {
		return cache_2294[cnt][cursum];
	}
	for (int i = 0; i < coins.size(); ++i) {
		int& pickCoin = coins[i];
        cache_2294[cnt][cursum] = min(cache_2294[cnt][cursum], solution(coins, cnt + 1, cursum + pickCoin));
	}
	return cache_2294[cnt][cursum];
}

djm03178 5년 전 0

코드는 반드시 전체를 올려 주세요. 이대로는 cache_2294가 올바르게 선언된 건지, MAX의 값은 무엇인지, 처음에 이 함수들을 어떻게 호출해야 하는지조차 알 수가 없습니다.

hojinseo 5년 전 0

앗,, 그렇네요

아래와 같이 코드를 작성했습니다.!

#include <iostream>
#include <vector>
#include <stack>
#include <memory.h>
#include <memory>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
constexpr auto MAX = 10000001;

int N_2294, K_2294;
int cache_2294[101][10001];
stack<int> debug;

bool canPick(int cursum, int pickCoin) {
	if (cursum + pickCoin > K_2294) {
		return false;
	}
	return true;
}
int solution(vector<int>& coins, int cnt, int cursum) {
	if (cursum > K_2294) {
		return MAX;
	}

	if (cursum == K_2294) {
		return 0;
	}
	 
	if (cache_2294[cnt][cursum] != -1) {
		return cache_2294[cnt][cursum];
	}
	cache_2294[cnt][cursum] = MAX;
	for (int i = 0; i < N_2294; ++i) {
		//int& pickCoin = coins[i];
		//if (canPick(cursum, pickCoin)) 
		{
			//debug.push(pickCoin);
			cache_2294[cnt][cursum] = min(cache_2294[cnt][cursum], solution(coins, cnt + 1, cursum + coins[i]) + 1);
			//debug.pop();
		}
	}
	return cache_2294[cnt][cursum];
}

int solution2(vector<int>& coins, int n, int cursum) {
	if (cursum > K_2294) {
		return MAX;
	}
	if (n == N_2294) {
		if (cursum == K_2294) {
			return 0;
		}
		return MAX;
	}
	if (cache_2294[n][cursum] != -1) {
		return cache_2294[n][cursum];
	}
	cache_2294[n][cursum] = min(solution2(coins, n + 1, cursum), solution2(coins, n, cursum + coins[n]) + 1);
	/*for (int i = 0; i < coins.size(); ++i) {
		int& pickCoin = coins[i];
		cache_2294[cnt][cursum] = min(cache_2294[cnt][cursum], solution(coins, cnt + 1, cursum + pickCoin));
	}*/
	return cache_2294[n][cursum];
}

int solution3(vector<int>& coins, int cnt, int cursum) {
	if (cursum == K_2294) {
		return cnt;
	}

	if (cache_2294[cnt][cursum] != MAX) {
		return cache_2294[cnt][cursum];
	}
	for (int i = 0; i < coins.size(); ++i) {
		int& pickCoin = coins[i];
		if (canPick(cursum, pickCoin)) {
			//debug.push(pickCoin);
			cache_2294[cnt][cursum] = min(cache_2294[cnt][cursum], solution(coins, cnt + 1, cursum + pickCoin));
			//debug.pop();
		}
	}
	return cache_2294[cnt][cursum];
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N_2294 >> K_2294;
	vector<int> coins;
	coins.resize(N_2294);
	memset(cache_2294, -1, sizeof(cache_2294));
	/*for (int i = 0; i < 101; ++i) {
		for (int j = 0; j < 10001; ++j) {
			cache_2294[i][j] = MAX;
		}
	}*/
	
	for (int i = 0; i < N_2294; ++i) {
		cin >> coins[i];
	}
	int res = solution(coins, 0, 0);
	res == MAX ? cout << -1 : cout << res;
	return 0;
}

djm03178 5년 전 0

solution이 호출될 때 cnt가 N_2294보다 커져도 cursum이 K_2294보다 작다면 그대로 배열에 접근할 것 같네요.

그리고 solution3로 호출해서 해보면 수행시간이 문제가 아니라 그냥 틀리네요.

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

문제

문제

출처

ICPC

밑의 두 함수의 차이를 잘 모르겠습니다

hojinseo 5년 전 0

djm03178 5년 전 0

hojinseo 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말