[이것이 코딩테스트다] 1이 될 때까지 (C++, Python)

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

 

1. N에서 1을 뺀다

2. N을 K로 나눈다

 

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

이는 N을 1로 만드는 최소 횟수이다.

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

입력조건
- 첫째줄에 N(2 <= N <=100,000)과 K(2 <= K <=100,000)가 공백으로 구분되며 각각 자연수로 주어진다.
이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력조건
- 첫째줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

 

#include <iostream>
using namespace std;

int main() {
	int n, k;
	int count = 0;
	cin >> n >> k;

	while (n != 1) {
		if (n%k == 0) {
			n = n / k;
			count++;
		}
		else {
			n = n - 1;
			count++;
		}
	}
	cout << count;

	return 0;
}

단순히 푸는 방법

 

#include <iostream>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	int count = 0;

	while (1) {
		int x = (n / k) * k;
		count += (n - x);
		n = x;
		if (n < k) //더이상 나눌 수 없으면 반복문 끝!
			break;
		n = n / k;
		count++;
	}

	count += (n - 1); // 이제 n이 1이 될 때까지 빼야하니(n-1번) 그만큼 더해준당.
	cout << count;
}

반복횟수를 줄인 방법

 

아직은 초보라서 단순히 푸는 방법밖에 떠오르지 않는데

더 노력해서 성장해보이겠습니다 저를 믿어주세요 (??)

 

---

 

 

n,k = map(int,input().split())

cnt = 0

while n != 1:
    if n % k == 0:
        n /=k
        cnt +=1
    else :
        n -=1
        cnt+=1

print(cnt)



#책 풀이 => n이 엄청 커졌을 때!
res = 0

while True :
    target = (n//k) * k #나누어 떨어지는 수 ex) (17//4) * 4 = 16
    res += (n-target) #일일이 -1씩 하는게 아니라 바로 계산해서 뺴주게
    n = target

    if n < k :
        break
    res += 1
    n //= k

res += (n-1) # n<k면 루프가 끝나니 1이 될 때까지 빼줘야함 => ex) n = 3 => (3-1)번
print(res)