알로그

백준 1463번 1로 만들기를 풀어보자. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 전형적인 DP문제이며, 우선 DP문제를 풀기 위해 점화식을 세워보자. 연산을 사용하는 횟수의 최소값을 구해야 하므로 아래와 같이 점화식을 세울 수 있다. D[N] = N을 1로 만들기 위해 사용한 연산의 최소 횟수 이때 사용할 수 있는 연산은 세가지이다. 만약 N이 3이라면 3으로 나눌 수 있고, 나눗셈 연산을 했으므로 연산횟수 1을 더 해준다 ex) D[3] = D[3/3] + 1 -> D[3] = D[1] + 1 이런식으로 각 연산마다 세울 수 있는 점화식은 아래와 ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net DP(Dynamic Programming)문제를 풀어보자. 문제에서 중요한 포인트가 있는데, 연속 두 계단씩 오를 수 있으며 마지막 도착계단은 반드시 밟아..

DP를 배울 때, 가장 첫 번째로 등장하는 문제라고 할 수 있다. https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net 피보나치 점화식은 문제에서 바로 주어지기 때문에, 딱히 설명하지는 ..