동적계획법

백준 27440번 “1로 만들기 3"은 10^18 범위의 매우 큰 정수를 세 가지 연산(3으로 나누기, 2로 나누기, 1 빼기)을 사용하여 1로 만들 때 필요한 최소 연산 횟수를 구하는 문제로, 입력 범위가 10^18에 달하기 때문에 일반적인 동적 프로그래밍 접근법(O(N) 시간, O(N) 공간)으로는 해결이 불가능하며, 재귀적 점화식과 해시 맵 기반 메모이제이션을 활용하여 O(log² n) 시간 복잡도로 효율적으로 해결해야 한다. 문제 설명 백준 27440번 - 1로 만들기 3 정수 N이 주어졌을 때, 세 가지 연산을 적절히 사용하여 1을 만드는 데 필요한 최소 연산 횟수를 구하는 문제다. ...