[리뷰] 그리디 - 1이 될때까지

github.com/ndb796/python-for-coding-test

ndb796/python-for-coding-test

이 문제는 유튜브에도 올라와 있으니 참고하세요. 그럼 코드 시작

n의 범위에 따라 문제 풀이 방식의 팁

O(n^3) : 500

O(n^2) : 2,000

O(nlogn) : 100,000

O(n) : 10,000,000

O(logn) : 10,000,000,000 이상

 

파이썬 : 직관적으로 푸는 법

import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
cnt = 0
while n!=1:
  if n%k ==0:
    n= n//k
  else:
    n-=1
  cnt+=1
print(cnt)

하지만 이 코드는 입력값 n이 상당히 클 경우 실행시간이 매우 크다. 위 코드에서 실행시간을 잡아먹는 코드는 일일이 n을 하나씩 빼는 것이다. 따라서 코드를 좀더 발전시켜야한다.

기본적인 아이디어는 n에 가장 가까운 k의 배수를 찾고 그 차이만큼 뺀다. 그리고 그 차이가 1의 단계들의 합이다.

import sys
n, k = map(int, sys.stdin.readline().rstrip().split())
cnt = 0

while True:
  p = n//k
  if p ==0:
    break
  tmp = (p) * k  #n에 가장 가까운 k의 배수
  cnt = cnt + (n-tmp) # 차이 갱신
  n = p # n 갱신
  cnt += 1 #곱하기 연산한거 1연산 더하기
  


cnt += (n-1) #1을 만드는 거기 때문에 1을 남겨야 한다
print(cnt)

 

c++ : 위 파이썬과 문법만 다르지 알고리즘은 동일하다.

#include <bits/stdc++.h>


using namespace std;

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

  while(1){
    int p = n/k;
    if(p==0) break;
    result += n - p*k;
    n = p;
    result ++;
  }
  
  result += n-1;
  cout<<result<<'\n';
}