[이것이 코딩 테스트다] 그리디 - 1이 될 때까지
그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법
✅ 문제
어떠한 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택하여 수해하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.
- N에서 1을 뺀다.
- N을 K로 나눈다.
N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력 예시
25 5
출력 예시
2
💻 코드
N, K = map(int, input().split())
count = 0
while True:
if N == 1 :
break
if N % K == 0 :
N = N // K
count += 1
else:
N -= 1
count += 1
print(count)
설계
N, K = map(int, input().split())
count = 0
while True:
if N == 1 :
break
if N % K == 0 :
N = N // K
count += 1
else:
N -= 1
count += 1
print(count)
N이 K로 나누어 떨어지면 N을 K로 나누고, 나누어 떨어지지 않는다면 N에서 1을 뺀다. 이 과정을 무한루프로 진행하고 N이 1이 되면 빠져 나온다.
➕ 문제 해설
답안
N, K = map(int, input().split())
result = 0
while True:
# target은 1에서 N까지의 수이고, K로 나눠질 수 있는 수 중 가장 큰 수
target = (N // K) * K
result += N - target
N = target
if N < K:
break
result += 1
N //= K
result += N - 1
print(result)
📝 정리
target = (N // K) * K
, result += N - target
코드를 통해 일일이 1씩 빼지 않고 N이 K의 배수가 되도록 하여 효율적으로 한 번에 빼는 방식을 사용할 수 있다.
Author And Source
이 문제에 관하여([이것이 코딩 테스트다] 그리디 - 1이 될 때까지), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@xxwb__/이것이-코딩-테스트다-그리디-1이-될-때까지
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
target = (N // K) * K
, result += N - target
코드를 통해 일일이 1씩 빼지 않고 N이 K의 배수가 되도록 하여 효율적으로 한 번에 빼는 방식을 사용할 수 있다.Author And Source
이 문제에 관하여([이것이 코딩 테스트다] 그리디 - 1이 될 때까지), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xxwb__/이것이-코딩-테스트다-그리디-1이-될-때까지저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)