백준 2293 : 동전 1

동전 1 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

4 MB

39927

17916

13432

44.928%

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

예제 입력 1 복사

3 10
1
2
5

예제 출력 1 복사

10

출처

• 어색한 표현을 찾은 사람: dbfldkfdbgml
• 빠진 조건을 찾은 사람: goodcrane3
• 데이터를 추가한 사람: jh05013

알고리즘 분류

• 다이나믹 프로그래밍

1               2             3               4             5             6             7               8             9              10

1	1	1	1	1	1	1	1	1	1
1	2	2	3	3	4	4	5	5	6
1	2	2	3	4	5	6	7	8	10

dp를 한줄로 만들어 놓고 계속 갱신해나가면 된다.

2차원배열같지만 

사실은 1차원배열로 봐야한다.

맨 위의 숫자는 돈, 1원2원3원

첫줄은 1개로만들수 있는 경우의 수의 합

두번째 줄은 2개로 만들 수 있는 경우의 수의 합

3번째 줄은 3개로 만들 수 있는 경우의 수의 합이다.

 

점화식을 잘 세워야한다.

첫줄에는 1개로 만들 수 있는 경우의 수가 들어간다

1원은 1, 2원은 1,1 3원은 1,1,1

이렇게 1개의 경우의 수 밖에 나오지 않는다.

2번째 줄부터 1,2원 2개로 경우의 수를 짜는데

2원은 무조건 크기때문에 2원부터 경우의 수를 더할 수 있다.

가령 2번째 동전이 5원이면 

5원은 1,2,3,4원을 만들때는 사용될 수 없다. 따라서 경우의 수를 추가할 수 없는 것이다.

무하튼 이것을 전제하에

if (j >= coin[i])
dp[j] += dp[j - coin[i]];

라고 점화식을 쓰면된다.