1이 될때까지1 [그리디알고리즘] 문제 - 1이 될 때까지 https://youtu.be/2zjoKjt97vQ?si=fGChNeo644FV1sFd 1이 될 때까지 문제 해결 아이디어 주어진 N에 대하여 최대한 많이 나누기를 수행 N의 값을 줄일 때 2이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음 1이 될 때까지: 정당성 분석 가능하면 최대한 많이 나누는 작업이 최적의 해를 항상 보장하는가? N이 아무리 큰 수여도, K로 계속 나눈다면 기하 급수적으로 빠르게 줄임 다시 말해 K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있음. 또한 N은 항상 1에 도달하게 됨 (최적의 해 성립) # 1이 될 때까지 #%% n = 17 k = 4 while n != 1: if n % k != 0: n -= 1.. 2024. 1. 30. 이전 1 다음
