[백준] 1463 | 1로 만들기 | C++
풀이의 핵심은 다이나믹 프로그래밍이다. 0. dp[i]의 값은 'i를 1로 만들기 위한 최소 연산 횟수'를 의미한다. 1. 2부터 n까지 i반복: dp[i]는 dp[i-1]에 1을 더한 값으로 초기화. 만약 i가 2의 배수라면: dp[i]=min(dp[i], dp[i/2]+1)로 초기화한다. 만약 i가 3의 배수라면: dp[i]=min(dp[i], dp[i/3]+1)로 초기화한다. 2. dp[n]을 출력한다. 0. dp를 벡터로 선언하면, OutofBounds에 안걸린다. 1. i가 6의 배수라면 2로도, 3으로도 나눠 떨어진다. 3으로 나누었을 때의 횟수가 더 적으므로 2부터 처리하도록 한다. 정답 소스코드 #include using namespace std; int n; int main() { ios..
2022.09.03