알고리즘97 ::거북이 카드만들기

ㅡ. 컨셉

거북이는 10이라는 숫자를 만들려고 한다. 그런데, 주어진 카드가 1,2,5 밖에 없다. 이럴 경우에 1을 10번 골라서 10을 만들거나 2를 두번 고르고 1을 고른뒤 5를 고르면 10이 만들어진다. 하지만 선택하는 수를 최소로 하고 싶다. 이런 경우 어떻게 해야 할까?

 

방법 : DP를 사용한다. 

 

int num = 10;
		int arr[] = new int[num+1];
		int cards[] = {1,2,5};
		for(int i=0; i<cards.length; i++) {
			for(int j=0; j<num; j++) {
				if(j+cards[i]>num) break;
				if(arr[j+cards[i]]==0) arr[j+cards[i]] = arr[j] +1;
				else {
					arr[j+cards[i]] = Math.min(arr[j+cards[i]], arr[j]+1);
				}
			}
		}
		System.out.println(arr[num]);