코후닝

알고리즘 분류: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 【 풀이 】 동적 계획법(DP, Dynamic Programming)을 이용하여 해결하는 문제이다. 그리고 이 문제 역시 여러 경우의 수를 생각하며 규칙성을 찾는 것이 중요한데, 이 규칙을 찾는 것이 어려웠던 것 같다. 우선 index를 피연산수, 값을 연산 횟수로 배열을 선언한 다음 1~10까지의 수를 검사하며 규칙을 찾아나갔는데, 규칙은 대충 다음과 같이 나왔었다. 2와 3으로 모두 나누어 떨어지지 않는 수: 1 + dp[index - 1] 2와 3으로 모두 ..