백준 1463 (1) 썸네일형 리스트형 DP(다이나믹 프로그래밍): 백준 1463 파이썬 문제: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이: 이 문제는 잘 알려진 다이나믹 프로그래밍 문제이다. 문제를 풀기 전에 함수가 호출되는 과정을 그림으로 그려보면 이해하는 데 도움이 된다. 예를 들어 n=6일 때, 함수가 호출되는 과정을 보면 다음과 같을 것이다. 확인해보면, 마찬가지로 f(2)와 같은 함수들이 동일하게 여러 번 호출되는 것을 알 수 있다. 이 문제에서 동일한 함수에서 구하는 값들은 동일해야 하므로 다이나믹 프로그래밍을 효과적으로 사용할 수 있다. 이제 문제에서 요구하는 내용을 점화식으로 표현해보자. 점화식 끝에 1을 더해주는 이유.. 이전 1 다음
