Algorithm/Baekjoon

[Baekjoon, Python] 2839번 : 설탕 배달

JMcunst 2022. 1. 25. 19:26
728x90
반응형

도입

백준 알고리즘 분류-그리디 알고리즘 첫 번째 문제이다.

백준 2839번 문제, 입력, 출력

백준 2839번 입출력 예제 1, 2, 3, 4, 5

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

풀이

1. 주어진 설탕의 kg(var_N)에서 3kg씩 빼주면서 봉지 수(rtn_bag)를 1씩 늘린다. var_N이 0 미만이 될때까지!

2. 설탕의 kg(var_N)이 5의 배수가 된다면, 5로 나눈 몫을 봉지 수(rtn_bag)에 더해주고 종료한다. 

코드

from sys import stdin

var_N = int(stdin.readline())  # 3 <= N <= 5000
rtn_bag = 0

while var_N >= 0:
    if var_N % 5 == 0:
        rtn_bag += var_N // 5
        print(rtn_bag)
        break
    var_N -= 3
    rtn_bag += 1
else:
    print(-1)

마무리

 오랜만에 풀어본 그리디 알고리즘, 예전에 풀어본 500원 100원 동전과 똑같은 문제.

 

 Github : https://github.com/JMcunst/Baekjoon-Algo/blob/main/python/2839.py

728x90
반응형