링크

거스름돈

문제 요약

  • 화폐단위와 거슬러줘야 하는 돈이 주어졌을때, 나오는 모든 경우의 수를 1000000007로 나누기.

초반 접근

  • 모든경우 확인 - 시간이 오래걸려서 효율성에서 0점이 나온다..
  • d[m]으로 m을 만드는데 나오는 경우의 수를 계산하기
    • 중복이 되는것을 거르지 못함.
    • d[m] = d[m-money[0]],d[m-money[1]],…
    • 위처럼 m을 만드는 경우들은 m에서 화폐단위들을 뺀것들에서 결정해야 하는데 중복처리를 생각 못했다.

해결법

  • 많은 고민이 있었다. 다이나믹 프로그래밍은 나한테 어렵기때문…
  • 처음에는 무작정 모든 경우를 나열하였다.
    • 하지만 시간만 걸릴뿐, 어떤 규칙도 어떤 패턴도 확인하지 못하였다.
  • 힌트를 얻고자 qna를 탐방하니 d[m][n]이라는 이중 배열의 힌트를 얻었다.
    • m은 화폐단위들의 index로 0부터 m번째의 화폐단위를 이용한다는 의미
    • n은 거슬러줘야 하는 금액
    • 합쳐서 m까지의 화폐단위를 이용하여, n을 거슬러주는 경우의 수가 된다.
  • 위의 힌트로 경우의 수를 채워 넣으니 한번의 패턴을 확인하고 이를통해 점화식을 정리 할 수 있었다.
    • 이걸 시간안에 어떻게 파악하는지…

알고리즘 간단 정리

  • ex)화폐단위는 money = [1,2,5], 거슬러 줘야 하는 금액이 N=5일때를 예시로 진행.
  • 아래는 d[m][n]을 기준으로 제작한 경우의 수를 표로 작성한것이다.
    • m까지의 화폐단위를 이용하여 n을 만드는 경우의 수
  • / 0 1 2 3 4 5
    0(1) 0 1 1 1 1 1
    1(1,2) 0 1 2 2 3 3
    2(1,2,5) 0 1 2 2 3 4
    • 그저 d[m][n]이라는 기준으로 작성하면 위와 같이 작성된다.
    • 여기서 패턴을 보자
      • 0번째 행(화폐단위가 1뿐일때)에서는 금액이 0이면 0이고 이후에는 한가지의 경우밖에 없다.
      • 1번째 행(1과2를 사용한 경우의 수)에서 거슬러 줘야 하는 금액이 “현재 가르키는 최대 화폐 단위(money[m])”보다 작으면 바로위의 d[m][n-1]과 같다.
        • d[m][n]===d[m][n-1]이 된다.
        • ex)화폐단위가 1원과 5원이 있을때, 4원을 거슬러주는건 1원으로 거슬러주는 경우뿐이다.
      • 1번째 행에서 금액이 2이상부터는 계산이 들어간다.
        • 먼저 d[m][n-1]의 값은 그대로 d[m][n]에 넘어온다.
        • 그리고 위의 행과 차이는 새로운 화폐단위 money[m]이 추가되었다는 것이다.
        • 추가적인 경우의 수는, n=(n-money[m])+(money[m])라는 경우를 생각하면 된다.
          • d[m][n]=d[m][n-money[m]]이 된다.
          • ex)d[2][3]=d[2][1]+d[1][3]
            • d[1][3] = {[111]}
            • d[2][1] = {[1]} -> {[1,2]}
              • 1원을 1,2로 만드는 경우느 [1]뿐이다. 1원에서 2원을 더하면 목표로 하는 3원이 된다. 그러므로 [1,2]라는 경우를 생각할 수 있다.
              • 둘이 생긴것은 다르지만 경우의 수로 생각하면 둘이 같은 1개의 경우를 생각 할 수 있다.
              • 따라서 d[m][n]을 계산하는데 d[m-1][n]의 수와 d[m][n-money[m]]의 수를 더하는 점화식을 생각할 수 있다.
        • 만약 d[m][n-money[m]]이 0이면 1더해주면된다.
          • 0인 경우는 money[m]혼자 해당 거스름돈을 거슬러준다는 의미
        • 결론 d[m][n]=d[m][n-money[m]]+d[m-1][n]이다.
  • 복잡하면 각각 경우의 수가 아닌 경우들로 작성하면 알아 보기 쉽다.
  • / 0 1 2 3 4 5
    0(1) 0 {[1]} {[1,1]} {[1,1,1]} {[1,1,1,1]} {[1,1,1,1,1]}
    1(1,2) 0 {[1]} {[1,1],[2]} {[1,1,1],[1,2]} {[1,1,1,1],[1,1,2],[2,2]} {[1,1,1,1,1],[1,1,1,2],[1,2,2]}
    2(1,2,5) 0 {[1]} {[1,1],[2]} {[1,1,1],[1,2]} {[1,1,1,1],[1,1,2],[2,2]} {[1,1,1,1,1],[1,1,1,2],[1,2,2],[5]}
    • 위의 경우의 수 표와 비교하면서 보면 이해하기 쉽다.
  • 마지막으로 100,000,007로 나눈 나머지를 정답으로 한다.

후기

  • 오랫동안 고민하고 고생하였다.
  • 다이나믹 프로그래밍 자체가 익숙치 않은것도 있지만, 이러한 패턴을 찾는데 많이 시간이 걸렸다.
  • 단순히 1차원 배열로 생각하여 중복을 생각 못하였고, 결과들을 나열해도 패턴을 파악하기 어려웠다.
  • 2차원배열이라는 힌트로 이러한 점화식을 생각하고 진행하였지만, 많은 시간과 노력이 있었다.
    • 힌트 얻자마자 바로 풀렸다….
  • 이러한 다이나믹 프로그래밍 문제는 이러한 점화식을 바로 찾냐 못찾냐로 시간내에 풀이가 가능한지를 판단 할 수 있으므로, 패턴파악이 제일 중요하다.

출처

  • d[m][n]
    • 거스름돈 n을 주기위해 화폐단위배열의 0~m을 사용하여 나오는 경우의 수.