-
2839. [Python]설탕 배달Python_알고리즘/Silver IV 2023. 1. 23. 22:53
1. 문제
https://www.acmicpc.net/problem/2839
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- 구현(약간의 탐욕 알고리즘)
3. 파이썬 코드
N = int(input()) # 시간 복잡도를 줄이기 위해 5의 배수일 경우 바로 출력 if N%5 == 0: print(N//5) # 5이하일 경우 3인 경우 바로 1 출력 외에는 -1 출력 되게 시간복잡도 절약 elif N < 5: if N == 3: print(N//3) else: print(-1) else: # check 라는 변수에 5로 나눈 몫을 넣고 reamin 이라는 변수에 5의 나머지 값을 넣음 check = N // 5 remain = N % 5 # 무한반복문을 시행하여 remain 값이 3으로 나누어 떨어지는지 판단함. while True: # 만약 나누어 떨어질 경우 5의 몫 + 3의 몫의 결과값이 정답이 되므로 아래 식 구현 if remain % 3 == 0: print(check + remain//3) break # 그 외의 경우 5로 나눴던 몫의 값을 1씩 감소해가며 최적의 수를 찾기 시작함. 하지만 N보다 커질경우는 탐색할 필요 없으므로 그 경우 break문 생성 else: remain += 5 check -= 1 if remain > N: print(-1) break
4. 문제를 풀고난 후 생각
- 가장 높은 값을 넣어가며 최적의 결과를 찾는 방식으로 탐욕 알고리즘에 대해서 정리한 후 문제를 풀었다.
- 시간 복잡도 절약을 위해서 5가 젤 큰값이므로 5의 배수인 경우 바로 출력되게 했으며 5이하에서 3인 경우를 제외하고는 -1을 출력 ( 결과값이 없기 때문에 )
- 그 외의 부분에서는 어떤 식으로 구현할지에 대해서 생각을 많이 했다.
- 모든 값들이 5로 떨어지고 3으로 떨어지면 좋겠지만 실제로 그렇지 않은 값들이 존재하기 때문에 이를 어떻게 구현할지 생각을 했고 먼저 5로 나눈 몫과 나머지를 통해서 무한루프로 모든 값들을 탐색하는 식으로 진행했다. ( 주석 설명 참조 )
5.문제를 푸는데 도움이 되는 지식
- 탐욕 알고리즘(Greedy Algorithm)
- 반복문
- 조건문
'Python_알고리즘 > Silver IV' 카테고리의 다른 글
1789. [Python]수들의 합 (0) 2023.01.30 11047. [Python]동전 0 (0) 2023.01.30 2217. [Python]로프 (0) 2023.01.29 11399. [Python]ATM (0) 2023.01.26 1459. [Python]걷기 (0) 2023.01.25