CC1 동전 교환(CC: Coin Change) 동전 교환(CC: Coin Change)은 다이나믹 알고리즘 중 하나입니다. CC는 동전의 종류들로 특정 금액을 만드는 경우의 수를 구하는 알고리즘입니다. 예를 들어서 1원, 2원, 5원, 10원 4가지 종류의 동전으로 10원을 만드는 경우의 수를 구해보겠습니다. 동전의 가치는 cost 배열에 넣었다고 생각하겠습니다. 즉, cost[] = {0, 1, 2, 5, 10} 입니다. 모든 경우의 수를 구하기 위해서는 2차원 배열이 필요합니다. d[i][j] = i가지 종류의 동전을 사용해서 j금액을 만드는 모든 경우의 수 입니다. 따라서 우리가 구하고자 하는 경우의 수는 d[4][10]이 됩니다. 이제 배열을 채워봅시다. 0행은 0원으로 j금액을 만드는 경우의 수라고 생각하변 됩니다. 0금액을 만드는 방법은 .. 2020. 2. 23. 이전 1 다음
