Baekjoon 9084 동전 JAVA

https://www.acmicpc.net/problem/9084

9084번: 동전

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%209084

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 동전 종류가 주어졌을 때 원하는 금액을 만들 수 있는 경우의 수를 구하는 문제다.

 

해당 문제는 dp를 이용하였고, 처음에 dp 배열을 2차원으로 두고 문제를 풀다가

그냥 1차원으로 둬서 갱신해주면 되겠다고 생각해서 그런식으로 문제를 해결했다.

 

동전 종류가 1원, 2원 2개고 만들고자하는 값이 8인 경우의 예제다.

1원의 경우 만드는 값 - 1은 이전값이기 때문에 값을 앞에서부터 채워준다

2원의 경우 기존 1원의 값에다가 2원으로 만드는 경우를 추가해주는데

1은 2원으로 만들수 없기 때문에 체크하지 않고 2원부터 체크하는데 현재 2는 1+1로 만들 수 있지만

2원으로도 만들수 있기 때문에 값이 1 증가하고 이런 식으로 쭉 진행된다

결국 점화식으로는 dp[j] += dp [j - coin[i]]이 사용되며 젤 마지막 값이 최종 개수가 된다.