[Baekjoon, Python] 11047번 : 동전 0
도입
백준 단계별 풀기 그리디 알고리즘 첫 번째 문제이다.
그리디 알고리즘
그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.
특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.
- 2. 최적 해 보장 불가
- 3. 효율성 개선
그리디 알고리즘 수행절차
1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택
현재 상태 최적화 기준 만족 여부 확인
2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인
현재 집합이 해가 될 가능성 검사
3. 해 검증 : 신규 구성 집합이 해인지 검사
문제가 아니면 1번으로 돌아가서 반복
풀이
1. 받는 것은 오름차순으로 받는데 큰 수부터 내림차순으로 푸는 것이 좋다고 판단하였다. 적합성 판단에서 최대한 큰가치의 동전이 연산을 덜 하기 때문이다. 배열m에 동전의 단위를 넣을 것이다. 오름차순으로 받아서 연산할 때(for문) 내림차순으로 불러낼 것이다.
2. 핵심 알고리즘이다. 목표 금액(k)에서 내림차순으로 나오는 동전의 단위(m[i])로 나눈 몫을 최종결과(num)에 더해준다. 그리고 목표 금액(k)에서 내림차순으로 나오는 동전의 단위(m[i])를 나눈 나머지를 다시 목표금액(k)로 잡는다. 그리고 반복한다.
코드
from sys import stdin
n, k = map(int, stdin.readline().split())
m = []
num = 0
for i in range(n):
m.append(int(stdin.readline()))
for i in range(n - 1, -1, -1): #range(시작,종료,얼만큼)
if k == 0:
break
num += k // m[i]
k %= m[i]
print(num)
마무리
C++로 풀었던 문제인데, 확실히 python이 더 편한 것을 느꼈다.