-
14916. [Python]거스름돈Python_알고리즘/Silver V 2023. 2. 2. 23:44
1. 문제
https://www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 512MB
- Greedy Algorith(탐욕 알고리즘)
3. 파이썬 코드
N = int(input()) cnt = 0 first_value = N # N 값이 5보다 작은 경우 2로 나눈 몫과 나머지 출력 if N < 5: cnt += N//2 N = N%2 if N == 0: print(cnt) else: print(-1) else: # N 값이 5보다 큰 경우 cnt 에 5로 나눈 몫을 넣고 나머지를 N에 넣어줘서 2로 똑같은 작업 수행 for i in [5,2]: cnt += N//i N = N%i # 무한루프 통해서 N == 0 인 경우 그대로 출력 아닌 경우 조건 생각 while True: if N == 0: print(cnt) break # 아닌경우 N 값이 초기 N 보다 커질때 -1 출력하고 break else: if N > first_value: print(-1) break # 그 전까지 N 에 5를 더해가며 cnt 값을 -1 씩해가고 나머지를 변수에 저장해서 0이 되는지 판단 else: N += 5 cnt -= 1 nam = N%2 if nam == 0: # 나머지가 0 이 될 경우 cnt 에 2로나눈 몫 값을 더해주고 출력 cnt += N//2 print(cnt) break
4. 문제를 풀고난 후 생각
- 이전에 풀었던 거스름돈 문제와 비슷한 방식으로 생각을 했었다.
- 가장 큰 돈을 먼저 계산해준 후 작은 돈을 계산하는 식으로 진행하지만 저번에 풀었던 방식이 기억안나 새롭게 생각해서 구현했다.
- 먼저 큰값으로 몫과 나머지를 구해준 후 무한 루프를 돌려 N 값이 나눠떨어지는지 나눠지지 않는지 판단한 후 나눠지지 않을 경우 큰 값들을 더하고 cnt 값을 빼가며 초기값보다 커지지않을때 까지 연산을 진행한다.
- 초기값보다 커졌을 때는 반복문을 break 하고 0이 되는 값을 찾은 경우는 2로나눈 몫을 cnt에 더해준다.
5. 문제를 푸는데 도움이 되는 지식
- Greedy Algorithm(탐욕 알고리즘)
'Python_알고리즘 > Silver V' 카테고리의 다른 글
2740. [Python]행렬 곱셈 (0) 2023.03.31 2535. [Python]아시아 정보올림피아드 (0) 2023.03.29 1817. [Python]짐 챙기는 숌 (0) 2023.03.27 1439. [Python]뒤집기 (0) 2023.02.01 2581. [Python]소수 (0) 2023.01.21