𝘚𝘭𝘰𝘸 𝘣𝘶𝘵 𝘴𝘵𝘦𝘢𝘥𝘺

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. DP를 이용하여 풀 수 있는 문제. 1. N이 3으로 나누어 떨어지면, 3으로 나눈다 ➡️ D[N] = D[N/3] + 1 2. N이 2로 나누어 떨어지면, 2로 나눈다 ➡️ D[N] = D[N/2] + 1 3. 1을 뺀다 ➡️ D[N] = D[N - 1] + 1 그러나 ..

'코딩 테스트를 위한 자료 구조와 알고리즘 with C++' 를 참고하여 작성하였습니다. 1. 동적 계획법 ; dynamic programming 1.1 개념 분할 정복 패러다임 개념을 확장한 것으로, 큰 문제를 작은 문제로 나누어 푸는 문제를 일컫는 말이다. 언뜻 문제를 보면 비슷하다 생각될 수 있지만, 분할 정복과 구분되는 동적 계획법만의 특성은 다음과 같다. 1. 중복되는 부분 문제(overlapping subproblem) 2. 최적 부분 구조(optimal substructure) 다음과 같은 속성을 만족해야 동적 계획법을 통해 문제를 해결할 수 있다. 전체 문제가 독립적인 부분 문제로 나뉘는 분할 정복 문제와 달리 동적 계획법에서는 중복되는 부분 문제가 반복적으로 등장한다. 또한 최적 부분 구..