백준 11047번 : 동전 0

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

문제

1 2 3

풀이


배열 입력 문제

  • 원래 동전의 합 문제를 그리디 알고리즘으로 풀 때는 우선순위가 높은 순으로 배열에 저장하는 방식을 사용하였다.
    ex. 500, 100, 50, 10 순으로
  • 그런데 이 문제에서는 입력받은 순서대로(동전 오름차순으로) 배열 요소를 입력하지 않으면 오답처리 되었다.
  • 그래서 원래는
    for i in reversed(range(n)):
    coins[i] = int(input())
    이런 식으로 코드를 작성하여 우선순위 순으로 동전을 저장하였었는데, 이후에는 그냥 입력받은 순서대로 저장하는 방식으로 바꾸었다.

몫과 나머지 활용

  • 처음 시도했던 것은 단순히 사용한 동전 만큼의 값을 초기 값에서 빼주는 것이었다.

  • 하지만 조금 더 좋은 방법이 있지 않을까 고민해 보았고 그 결과 몫과 나머지를 활용한다면 굳이 num이라는 변수에 별도로 값을 저장하지 않아도 되겠다는 결론이 나왔다.

완성된 코드

댓글남기기

참고