[백준 01463] 1로 만들기 [C/C++]

문제

 

https://www.acmicpc.net/problem/1463

---

풀이

N을 1로 만들기 위한 연산을 최소화하는 문제다.

dp[i] : i를 만들기 위한 최소 연산 횟수

• 기본적으로 dp[i]는 dp[i - 1]에 1을 더해 만들 수 있다, dp[i] = dp[i - 1] + 1
  
• i가 만약 2 또는 3의 배수라면, 1, 2번 연산에 의해 곱셈으로 계산하는게 이득이다.
  단, 2보다는 3으로 곱셈하는 것이 연산 횟수가 더 최소화되므로 dp 갱신 순서에 유의하자.

---

소스코드

보기