목록백준1463 (1)

하나씩 알아가기

[BOJ_1463] 1로 만들기

10을 세 가지 연산을 이용하여 1로 만든다고 할 때 모든 경우 중에 가장 작은 수를 찾아내야 합니다. 10 -> 9 -> 8 -> 7 -> ... -> 1 (x) 10 -> 9 -> 3 -> 1 (o) * 점화식: 수열의 각각의 항들의 관계를 나타낸 식 모든 경우의 수를 고려할 경우 점화식을 떠올리는 방법을 생각해 내는 것이 좋은 방법이 될 수 있습니다. 이 문제의 경우 수를 줄일 수 있는 연산은 세 가지 밖에 없으므로 점화식은 이 경우를 포함하여 적어줘야 합니다. f(n) = 1 + min(f(n/3), f(n/2), f(n-1)) 그런데 가령, f(n/3)이 반드시 존재하는 값은 아닐 수 있지만 이렇게 점화식 형태로 표현이 가능한 경우 다이나믹 프로그래밍을 적용하여 문제를 해결하는 것이 가장 일반적..
알고리즘 2021. 1. 21. 11:47
이전 Prev 1 Next 다음