[문제해결기법] 카드 조합하기

DP를 이용하면 된다!! -> 동적 계획법

보통 동적계획법을 사용할 때에는 모든 경우의 수를 다 돌아야할 때이다.

동적 계획법을 사용시 시간을 줄이려면 cache를 이용하여 결과값을 저장하여 놓는 것이 좋다.

이미 돌았던 경우의 수라면 반복해서 경우의 수를 구할 필요없이, 바로 값을 return해주면 된다.

따라서 보통 이중배열을 사용하여 cache를 만들고 저장한다.

이 문제는 나에게 매우 어려웠던 문제이다.

각 숫자마다 가지고 있는 카드의 수도 제한되어 있고, 모든 경우의 수도 돌아야하기 때문이다.

무엇보다 무엇을 이중배열의 두개의 변수를 무엇으로 정해야할지 몰라서 많은 고민을 했다.

http://yejin0730.tistory.com/ 이 친구의 도움을 받았다!!!

알고리즘이 복잡하기에 길게 설명해보려고 한다.

우리는 "목표 숫자에서 사용한 카드의 수를 뺀 나머지 수"와 "사용한 카드"를 cache의 두개의 변수로 사용할 것이다.

그리고 경우의 수를 저장할 것이다.

그럼 예를 들어 각 카드가 5개씩 있다고 하고 4를 돌려보자.

위와 같은 방법으로 돈다 1부터 살펴보자

먼저 1의 카드가 한 장도 없을 때 나머지는 4이다.

     2의 카드가 한 장도 없을 때 나머지는 4이다.

     4의 카드가 한 장도 없을 때 나머지는 4이다.

하지만 8은 4보다 크므로 1장도 사용하지 않는다 ( if (card의 번호>남은 수) return 0;)

이것이 맨 윗줄의 초록색이다 -> 그렇다면 카드가 8일때 총 경우의수는 0이므로 0을 리턴한다.

4의 카드가 0장일 때 0번의 경우의 수로 4를 만들 수 있다.

그렇다면 4의 카드가 1장일 때는 어떨까?

4의 카드가 1장이면 우리가 목표하는 수 4와 같으므로 1개의 경우의 수가 더해졌다

만약 4의 카드가 2장이면 목표하는 수보다 더 큰 수가 나온다. 그러므로 

4의 카드를 0장썼을 때와 1장썼을 때의 경우의 수를 더하여 return한다

이제 2의 카드로 넘어왔다.

2의 카드가 0개 사용되었을 때 1번의 경우의 수가 가능하다.

2의 카드가 1장 사용되었을 때는 어떨까?

2의 카드가 1장이면 우리가 목표하는 수 4에서 2를 한장 썼으므로 2가 되고

이 수를 4의 카드가 있는 곳으로 넘겨준다

하지만 4는 목표하는 수 2보다 큰 수이다. 그러므로 1장도 사용하지 않는다.

목표하는 수가 2일때 사용하는 4의 카드의 수는 0장이므로 0장을 리턴한다.

2의 카드가 1장일때 0번의 경우의 수가 가능하다

2의 카드가 2장이면 목표하는 수 4와 같다.

그러므로 1+0+1 즉 2가 리턴된다.

이제 1의 카드로 넘어왔다.

1의 카드가 0개 사용되었을때 2번의 경우의 가 가능하다.

1의 카드가 1장 사용되었을때, 2장 사용되었을 때 ... 5장 사용되었을 때의 경우를 위와같이 구하면

정답인 4가 리턴된다.

이와 같은 방법으로 DP를 사용하면 된다.

코드는 아래와 같다.

#include <iostream> #include <fstream> #include <vector> using namespace std; vector<vector<int>>card; int card_count; int check_card(int index,int rest) { int count = 0; if (pow(2, index) > rest) return 0; //만약 2의 index승 > 나머지 수 -> return 0 //나머지가 없음 if (card[rest][pow(2, index)] != -1) return card[rest][pow(2, index)]; //만약 이미 센 카드라면 그 값을 return for (int j = 0; j <= card_count; j++) { if (!(rest - pow(2, index)*j)) return card[rest][pow(2, index)] = count + 1; //만약 우리가 구해야하는 나머지 값과 같다면 count에 1을 더하고 return if ((rest - pow(2, index)*j) < 0) return card[rest][pow(2, index)] = count; //만약 구해야하는 나머지가 0보다 작다면 -> 그냥 return count += check_card(index + 1, rest-pow(2,index)*j); //아니면 그 count값을 계속 더해줘야한다. } return count; //현재 count값 } int main() { ifstream fcin,fcout; fcin.open("B_input.txt"); fcout.open("B_output.txt"); int for_count; fcin >> for_count; while (for_count--) { int propose; fcin >> card_count >> propose; int row_count = 1; while (row_count <= propose) row_count <<= 1; card = vector<vector<int>>(propose + 1,vector<int>(row_count,-1)); //[rest][card] int answer; fcout >> answer; if (answer != check_card(0, propose)) cout << "wrong" << endl; } cout << "perfect" << endl; system("pause"); }