-
N과 K를 입력받아, N을 K로 나누어 1이 되게 하는 그리디 알고리즘 문제.
단, N을 K로 나눌 수 없을 때엔 -1을 반복합니다.
예제 코드
# N, K공백을 기준으로 구분하여 입력 받기 n, k = map(int, input().split()) result = 0 while True: # N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기 target = (n // k) * k result += (n - target) n = target # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출 if n < k: break # K로 나누기 result += 1 n //= k # 마지막으로 남은 수에 대하여 1씩 빼기 result += (n - 1) print(result)
target에 (n//k) * k를 해서, n이 k로 나눠지는 인접한 수를 구합니다.
이를 입력된 n의 값에 빼서, -1 을 몇 번 하면 나눌 수 있는지 알 수 있습니다.
그 후, 그 숫자를 반복 횟수(result)에 저장합니다. 그 수를 n 에 저장합니다.
n이 k보다 작아졌을 때, 반복을 그만합니다.
이 과정을 마치게 되면 k로 n을 나눠주어 숫자의 크기를 점점 줄여나가면 됩니다.
마지막에 result에 n-1 값을 더해줍니다.
'개발 > 알고리즘' 카테고리의 다른 글
알고리즘_ 순열 검사, n의 배열에 중복 값 확인. (0) 2021.10.08 알고리즘_ 자릿 수 더하기 (0) 2021.10.08 알고리즘_ 평행한 사각형에서 3개의 점과 나머지 한 점 (0) 2021.10.08 [백준/BOJ] JAVA_1330번 숫자 비교 하기 (자바) (0) 2021.07.29 [백준/BOJ] JAVA_2588번 곱셉 과정 출력하기 (자바) (0) 2021.07.27 댓글 (비로그인 댓글 허용하지 않습니다.)