지우쓰 개발일기

문제 풀이 DP 알고리즘 문제들 중 유명한 문제라고 한다. 찾아보기 전엔 몰랐음 ㅎ; 반복문으로 DP를 풀 수도 있지만 반복문은 딱 봤을 때 이해하기 힘들어서 재귀로 풀었다. 재귀가 실행속도는 조금 더 느리긴 한데, 이름도 더 만족스럽게 지을 수 있고 이해도 더 잘됐다. 1번부터 N번까지 행렬을 모두 곱할 때의 최소 카운트를 구하는 문제다. DP는 큰 문제를 작은 문제로 쪼개는 것이니까, 작은 범위에서부터 최솟값을 구하고 그 최솟값을 바탕으로 다음 범위의 최솟값을 구하면 된다. 각 변수들은 다음을 의미한다. rows[i]: i번째 행렬의 열 갯수 cols[i]: i번째 행렬의 행 갯수 dp[i][j]: i번부터 j번까지의 행렬을 곱할 때의 최소 카운트 getMinCount() 내부의 반복문을 돌 때 모든..

문제 풀이 1원부터 k원까지 단계적으로 추가해가면서 최종값을 구해야 겠다는 생각은 금방 들었는데, 그 안에서 동전도 단계적으로 추가해야 겠다는 생각을 하는 데에 시간이 조금 걸렸다. 모든 동전을 다 사용하는 경우의 수를 한 번에 구하는 것은 불가능하다. 따라서 사용하는 동전을 제한하고 하나씩 늘려감으로써 최종 값을 구해야 한다. 즉, 동전 하나(coins[1])만 사용했을 때, 1원부터 k원까지 전체 value를 만들 수 있는 경우의 수를 구하고, 동전 두개(coins[1], coins[2])를 사용했을 때, 2원부터 k원까지의 경우의 수를 구해야 한다. 이렇게 전체 동전을 사용할 때까지 반복하면 모든 동전을 사용했을 때 k원을 만들 수 있는 경우의 수를 구할 수 있다. 각 변수에는 다음을 저장한다. -..