알고리즘 문제 - 1이 될때까지

문제 - 1이 될때까지

• 어떠한 수 N이 1이 될떄가지 다음의 두 과정 중에 하나를 반복적으로 선택하여 수행하려고 한다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

• 두 번째 연산은 N이 K로 나누어질때만 선택할 수 있다.

• 예를 들어서 N이 17, K가 4라면 1번의 과정을 1번하면 16이 되고 이후 2번의 과정을 2번하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다.

• N과 K가 주어질 때, N이 1이 될떄까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성하라.

제한 사항

아이디어

그리디

• K로 나눌 수 있는지 보고, 나눌 수 없으면 1을 뺀다.
• N이 1이 될때까지 위의 과정을 반복한다.

재귀

• K로 나눈 경우와, 1을 뺀 경우를 선택한다.
• 그리고 결과적으로 더 작은 값을 선택한다.

코드

def solution(n: int, k: int) -> int:
    """
    :param n: 특정한 수
    :param k: 나눌 수
    :return: 수행한 최소 횟수
    """
    tot = 0
    while not n == 1:
        if n % k == 0:
            n //= k
        else:
            n -= 1
        tot += 1
    return tot


def solution2(n: int, k: int) -> int:
    result = 0

    while n >= k:
        while n % k != 0:
            n -= 1
            result += 1
        n //= k
        result += 1

    while n > 1:
        n -= 1
        result += 1
    return result

def solution3(n: int, k: int) -> int:
    cnt = 0

    while not n <= 1:
        if n % k == 0:
            n //= k
            cnt += 1
        else:
            target = (n // k) * k
            cnt += n - target
            n = target

    return cnt


if __name__ == "__main__":
    n, k = map(int, input().split())
    print(solution(n, k))

더 나은 방법

• 조금 더 효율적으로 풀 수 있는 방법이 있다.

• 입력이 적을 때는 일일이 하나씩 빼도 문제가 없지만, 큰 숫자를 빼야하는 경우에는 N이 K의 배수가 되도록 효율적으로 한번에 빼는 것 이 좋다.

• 앞으로 하나씩 빼는 패턴이 보이면 한번에 뺄 수 없는지 고민을 해봐야겠다.

참고 문헌

• 이것이 취업을 위한 코딩테스트다, 나동빈, 한빛미디어