[Python]알고리즘/이코테 2021
[그리디 알고리즘] 문제1 - 1이 될 때까지
1이 될 때까지 1) 문제 해결 아이디어 N에 대해 최대한 많이 나누기(2번 연산)을 수행 N의 값을 줄 일 때, 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음 2) 정당성 분석 Q. 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장할 수 있는가? K가 2 이상이면 K로 나누는 것이 1을 빼는 것보다 항상 N을 빠르게 줄일 수 있음 3) 소스코드 n, k = map(int, input().split()) count = 0 # 최소 횟수 while True: # 탈출 조건 if(n == 1): break # n이 k로 나누어 떨어지면 나누기 if(n % k == 0): n /= k # n이 k로 나누어 떨어지지 않으면 빼기 else: n -= 1 count += ..
