개발하는 자몽

백준에서 DP의 기초 문제인 1463번을 풀어보았다. 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 해당 문제를 보고 어떻게 DP로 풀어야겠다! 는 생각이 바로 들진 않았고, 처음에 그냥 무작정 반복문과 if-else의 조합으로 풀었다. 실패했다. if-else가 아닌 이유 if-else가 아닌 모든 경우의 연산을 시도하고 가장 작은 연산 횟수를 택해야 하기 때문에 모두 if로 행하고 Math.min으로 비교했을 때 가장 작은 값을 택한다. 동적 계획법으로 풀 수 있는 이유 여러 해설을 봤는데 가장 이해가 잘 되는 글은 아래 블로그였다. 백준 알고리즘 1463번 문제풀이 1로 만들기 문제 정수 X에 사용할 수 ..