그리디 알고리즘

• 탐욕법
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구
• 그리디 해법은 그 정당성 분석이 중요
  • 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

문제 1 : 거스름 돈

문제 2 : 1이 될 때까지

n, k = map(int, input().split())

result = 0

while True :
	target = (n//k) * k
	result +=

문제 3 : 곱하기 혹은 더하기

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때,
• 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며
• 숫자 사이에 ‘X’ 혹은 ‘+’ 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수
• 예를 들어 02984 라는 문자열이 주어진다면
• ((((0+2) x 9 ) x 8 ) x 4 ) = 576