수들의 합

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

풀이

  • 런타임 에러가 계속 났음

  • 원인

    • 자료형.
    • 문제의 입력으로 자연수 S(1≤S≤4,294,967,295)가 주어진다.
    • int의 범위를 넘기 때문에 런타임 에러가 계속 났음
  • 해결

    • long형으로 입력 받음
  • 쉬운 문제라도, 문제의 조건을 잘 확인해야함

Read more

설탕배달

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

풀이

  • d[i]

      ikg을 담을 수 있는 최소 봉지 수
    
  • ex) 6kg

      0 + 6 => 6을 3kg짜리 봉지 2개로 담을 수 있음 => d[6] = 2
    

    ​ 1 + 5 => d[1]== -1 => X
    ​ 2 + 4 => d[2]== -1 => X
    ​ 3 + 3 => d[6] = d[3] + d[3] = 1

  • ex) 10kg

      0 + 10 => 10을 5kg짜리 봉지 2개로 담을 수 있음 => d[10] = 2 
    

    ​ 1 + 9 => d[1]== -1 => X
    ​ 2 + 8 => d[2]== -1 => X
    ​ 3 + 7 => d[7]== -1 => X
    ​ 4 + 6 => d[4]== -1 => X
    ​ 5 + 5 => d[5] == 1 => d[10] = d[5] + d[5] = 2

  • 위와 같이, 앞 단계에서 사용된 값이 재사용된다. 따라서 DP

  • 더 간결하게 어떻게 짤 수 있을까?

Read more

동전

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

풀이

  • ex) 1원, 5원, 10원이 있다. 만들어야하는 동전은 100원

  • 1원을 이용해서

      d[1] : 1원을 만드는 경우의 수 => 1원, d[0] => 1
    

    ​ d[2] : 2원을 만드는 경우의 수 => 1원, d[1] => 1
    ​ d[3] : 3원을 만드는 경우의 수 => 1원, d[2] => 1
    ​ …
    ​ d[100] : 100원을 만드는 경우의 수 => 1원, d[99] => 1

  • 5원을 이용해서

      d[5] : 5원을 만드는 경우의 수 => (1원, d[4]) + (5원, d[0]) => 1 + 1 => 2
    

    ​ d[6] : 6원을 만드는 경우의 수 => 1원, d[5] => 1
    ​ d[7] : 7원을 만드는 경우의 수 => 5원, d[2] => 1
    ​ …
    ​ d[9] : 9원을 만드는 경우의 수 => (1원,d[8]) + (5원, d[5])
    ​ …
    ​ d[100]

  • 10원을 이용해서

      d[10] : 10원을 만드는 경우의 수 => (1원,d[9]) + (5원, d[5]) + (10원, d[0])
    

    ​ …
    ​ d[100]

  • 위와 같이 전 단계에 나온 결과값을 재사용할 수 있다. 때문에 DP 문제이다.


Read more