글 읽기 - dp에서 [x] + [y]이랑 [y] +[x] 중복을 어떻게 구별해야하나요?

rktkek456 5년 전 0

2 5

이렇게 입력을 하면

cache 값 : 0 1 2 3 4 5

경우의 수 : 0 0 1 1 2 2

그래서 2와 3을 이용해서 5가 나오는 경우의 수를 구하면 2가 나오는데

이 2가 cache[2] + cache[3]이랑 cache[3] + cache[2] 둘을 다 카운트 하는데

이 중복을 어떻게 제거 할 수 있을까요...ㅠ

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

void getAns(const int& targetValue, const vector<int>& groupOfPrice) {
	vector<long long int> cache(targetValue + 1, 0);
	for (int i = 0; i < groupOfPrice.size(); ++i) {
		cache[groupOfPrice[i]] += 1;
	}

	for (int i = 0; i < cache.size(); ++i) {
		for (int j = 0; j < groupOfPrice.size(); ++j) {
			if (cache[i] != 0 && i + groupOfPrice[j] <= targetValue) {
				cache[i + groupOfPrice[j]] = cache[i] + cache[groupOfPrice[j]];
			}
		}
	}
	cout << cache[targetValue];
}

int main() {
	vector<int> groupOfPrice;
	int numberOfPrice, targetValue;
	cin >> numberOfPrice >> targetValue;

	int price;
	for (int i = 0; i < numberOfPrice; ++i) {
		cin >> price;
		groupOfPrice.push_back(price);
	}
	getAns(targetValue, groupOfPrice);
}

djm03178 5년 전 1

동전의 순서를 정해서, k번째 동전까지만 사용하는 경우의 수를 먼저 다 구하고 k+1번째 동전으로 넘어가보세요.

rktkek456 5년 전 0

만약에 동전을 2개라 하면 2개 쓰는 경우만 다 구하고 그 다음 3개 4개 쓰는 경우를 구하라는 말인가요...?

djm03178 5년 전 2

아무 두 종류만을 말하는 것이 아니라, 순서를 정했을 때 첫 두 종류만을 구하는 것입니다. 예를 들어 동전이 a, b, c라는 종류들이 있다면,

1. a 동전만 (개수 상관 없이) 사용했을 때의 경우의 수

2. a 동전과 b 동전을 사용했을 때의 경우의 수

3. 세 동전을 모두 사용하는 경우의 수

의 순서로 구하면 됩니다.

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

문제

문제

출처

ICPC

dp에서 [x] + [y]이랑 [y] +[x] 중복을 어떻게 구별해야하나요?

rktkek456 5년 전 0

djm03178 5년 전 1

rktkek456 5년 전 0

djm03178 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말