교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 3 그리디
실전문제 3-4 1이 될 때까지 99p
1이 될 때까지
문제
어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 함
단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있음
-
N에서 1을 뺀다.
-
N을 K로 나눈다.
N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성
입력
첫째 줄에 N(2<= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어짐
이때, 입력으로 주어지는 N은 항상 K보다 크거나 같음
출력
첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력
입력 예시
3 3
3 1 2
4 1 4
2 2 2
출력 예시
2
풀이
접근 1
- 나누고 안되면 빼자
Note
풀면서도 이거 아닌데...생각은 했는데 ㅋㅋ..
제출 1 - 정답
n, k = map(int,input().split())
cnt=0
while n !=1:
if n%k==0:
n = n//k
cnt+=1
else:
n-=1
cnt+=1
print(n)
print(cnt)
오답노트
이 문제도... 책한테 뚜들겨 맞았다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 샘플이 엄청 큰 수가 될 때를 고려하는 사고를 가져야 될 것 같다... 진짜....
우선 풀이에서 나눠떨어지는 값중 최댓값?으로 target으로 잡고 (n//k)*k
target에 대한 나머지 값은 result에, target은 n에 넣고
n을 계속 k로 나누다가 안나눠질때의 남은 값을 result에 더해서 결론을 낸다...
진짜 이렇게 생각을 어케...하는거지요? ㅜㅜ
진짜 반성... 나도 진짜 꼭... 샘플 클 때 효율적인 코드 뭔지 꼭 고민해보면서 문제 풀어야겠다... 돌리면서 1 하나씩 빼는거...대박 멍청 ㅠㅠ
- 책에 있는 솔루션
# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
target = (n // k) * k
result += (n - target)
n = target
# N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)결과
- 풀이시간 : 4분
References
이것이 코딩 테스트다 with 파이썬 - 나동빈 저
