목차
반응형
내 풀이 - 1차
"""
### 동빈나 <이것이 코딩테스트다> 실전 문제
## 그리디 알고리즘 - 3. 1이 될 때까지
# 난이도 '하' / 시간제한 1초 / 메모리 제한 128MB / 기출: 2018 E 기업 알고리즘 대회
# 풀이 시간제한: 30분
"""
"""
N: 1로 만들 숫자
K: N을 나눌 숫자
Result: 주어진 N이 1이 될 때까지 걸리는 최소 횟수
"""
N, K = map(int, input().split())
result = 0
while True:
if N == 1:
break
if N % K == 0:
N /= K
else:
N -= 1
result += 1
print(result)풀이 설명
- 1을 빼거나 K로 나누는 작업을 수행하여 N이 1이 되도록 하는 최소 횟수를 구해야 함
- K로 나누는 작업을 최대한 많이 하는 것이 포인트
- while문 안에서 K로 나눌 수 있을 경우에는 계속해서 나누고, 그렇지 않을 경우에만 1을 뺌
내 풀이 - 2차 (해설 본 후)
N, K = map(int, input().split())
result = 0
while True:
# N이 K의 배수가 될 때까지 1씩 빼기
target = (N//K) * K
result += (N - target)
N = target
# N이 K보다 작아져서 더 나눌 수 없을 때 break
if N < K:
break
result += 1
N //= K
# 남은 수에 대해 1씩 빼기
result += (N - 1)
print(result)풀이 설명
- N이 엄청 큰 수일 경우에도 빠르게 처리하려면 N과 가장 가까운 K의 배수를 찾아 그 차를 구하여 결과에 더하고, 이후 나누는 작업을 계속 진행
- 즉 1을 빼는 연산을 한 번에 구해서 result에 더해주는 것
궁금한 점
- 마지막에 "result += (N - 1)"은 "result -= 1"로도 충분할 것 같은데 (주어진 테스트 케이스에서는) 굳이 N-1이어야 하는 이유가 있을까?
- 현재 주어진 테스트 케이스에서는 while문을 빠져나올 때 이미 N == 0인 상태임
- N이 while문을 빠져나올 때 0이 아닌 테스트 케이스가 주어지면 이해하기가 좀 더 편할 것 같다.
궁금증 해결!
같은 궁금증을 가지고 계시던 분이 나동빈님 GitHub에서 질문을 해주셨다.
결론은 result -= 1이 되어도 무방하다는 것. 그냥 구현의 차이일 뿐이었다.
반응형
