p.99_실전문제 : 1이 될때까지.

문제는 다음과 같다. 

아래는 처음 내 풀이 였고, 30분 안에 풀지 못하였고 아래 4가지 궁금증이 생겼다.

# 그리디 실전 문제 # 1 (난이도 : 하)
N = 17
K = 4
count = 0 

for num in N/K:
    if N % K == 0:
       num += N/K
    else:
        num += N-1 

# 초반에 N, K, count 값을 초기화 하는 건 ㅇㅋ
# 횟수를 구할 때 까지 반복할텐데 구간을 어떻게 정하지?
# 그리고 if문을 2번 써야할 거 같은 데 어떻게 하고
# 횟수는 어떻게 올리냐

그리고 아래는 답안을 본 것이다.

# 그리디 실전 문제 # 1 답안_ver1
# n과 k 입력 받기, result 초기화 
n, k = map(int,input().split())
result = 0

# N에서 1을 빼는 것보다 나누는 게 더 빠르니깐 나누는 것부터 한거
# n이 k보다 크거나 같을 때까지 반복
while n>=k:
    while n % k !=0:  # n을 k로 나눈 나머지가 0이 아닐 때 까지 반복 
        n -= 1        # n에서 1를 빼고
        result += 1   # result에 1를 더한다.
    n //= k           # n을 k로 나눈 몫을 n에 저장한다.
                      # 15를 5로 나눈 몫(3)을 n에 저장한 뒤 반복임.
    result += 1       # result에 1을 더한다.

# 나누다보면 k가 더 커진 순간에는 이놈을 사용
# n = 15, k=5 라면 1번째 때 n =3, k =5가 됨 그럼 아래로 가서 계속 빼주는거
while n > 1:          
    n -= 1           
    result += 1

# 코드 실행이 끝나면 따로 모든 result 더하지 않아도 연산횟수가 누적되어 있음.
print(result)

# 그리디 실전 문제 # 1 답안_ver2
n, k =map(int,input().split())
result = 0

while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    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)

그리고 아래는 복습 겸 다시 풀이 하였다.

# 복습 겸 혼자서 다시 풀이
n, k = map(int,input().split())
cnt = 0

# n이 k보다 클 때
while n >= k:
    while n%k != 0:
        n -=1
        cnt +=1
    n //=k
    cnt +=1

while n<k:  
    n -=1
    cnt += 1
# 위에가 안되는 게 15 3 이라고 했을 떄
    1 번쨰 15/3 =5
    2 번째 5-1=4
    3 번째 4-1=3
    4 번째 3/3=1
    5 번째 1-1=0
    6 번째 -1

Q) 이러한 아이디어가 정당한가?

• 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있을까요?
• N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다.
• 다시 말해 K 가 2 이상이기만 하면, K로 나누는 것이 1을 뺴는 것보다 항상 빠르게 N을 줄일 수 있다. 또한, N은 항상 1에 도달하게 됩니다. (최적의 해 성립)

그리고 아래는 chat gpt 답을 보았는 데 처음에 내가 풀고자 하는 방향과 가장 잘 맞아 첨부한다.

Line3에서는 내가 생각한 고민한 문제였다. 초보자들이 가장 쉽게 이해할 수 있는 풀이지 않을 까 싶다.

# 그리디 실전 문제 # 1 답안_ver3(feat.Chat Gpt)
# 개인적으로 제일 마음에 드는 답변임. 처음에 내가 시도할려고 한 방향과 맞음.
# 근데 n은 1보다 계속 크지 않나. 아 아니다. n=2에서 1빼면 1이고 while문을 빠져나오겠네.
n, k = map(int, input().split())
result = 0

while n > 1:  # 조건 1: N이 1보다 클 때까지 반복
    if n % k == 0:  # 조건 2: N이 K로 나누어 떨어지면
        n //= k  # N을 K로 나눔
        result += 1
    else:
        n -= 1  # N에서 1을 뺌
        result += 1

print(result)  # 결과 출력