1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

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

 

질문

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

 

 

코드로 구현

아래는 파이썬으로 구현한 코드이다.

N,K=map(int,input().split())

result=0

while True:
          if N%K==0:
                    N/=K
          else:
                    N-=1
          result+=1
          if N==1:
                    break
print(result)

 

아래는 C/C++으로 구현한 코드이다.

#include<iostream>

int main() {
	int N, K;
	int result = 0;
	std::cin >> N >> K ;

	while (true) {
		if (N % K == 0) {
			N /= K;
		}
		else {
			N -= 1;
		}
		result++;
		if (N == 1) break;
	}

	std::cout << result;
	return 0;
}

 

 

www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고