[25418번] 정수 a를 k로 만들기

문제링크 : https://www.acmicpc.net/problem/25418

 

 

문제분석

 

사용할 수 있는 연산은 +1 or  *2 뿐이다.

 

이때 최소 연산 수를 구하면 된다.

 

 

문제풀이

 

dp[A] = 0으로 초기화를 한다.

 

dp[i] = dp[i-1] + 1 로 기본적으로 업데이트를 해준다.

 

만약 i가 짝수라면 dp[i] = min(dp[i], dp[i/2] + 1)로 갱신을 해준다.

 

 

 

여기서 처음에는 매 연산마다 dp[i/2]를 고려해서 설계하려 했다. 그러니 연산이 생각보다 복잡해졌다.

 

사실 K가 커질수록 곱셈 연산은 dp 연산을 하면서 생각보다 자주 등장하지 않게 된다. 

 

따라서 매번 곱셈 연산을 고려하기 보다 +1로 기본 업데이트를 해주고 곱셈 연산을 고려해야될 경우만 따로 확인하는 것이 훨씬 

 

더 좋은 아이디어였다.