반응형 다이나믹프로그래밍2 [DP] 백준 2579 계단오르기(Climbing Stairs) BackJoon #2579 - 계단오르기(Climbing Stairs) https://www.acmicpc.net/problem/2579 대표적인 DP문제입니다. DP[N] 을 N개 계단을 계단오르기 규칙에 의해 얻은 가장 큰 점수라고 하겠습니다.N번째 계단은 무조건 밟아야 하기 때문에 N번째 계단이 1번 연속인 경우! N번째 계단이 2번연속인 경우! 이 2가지 경우를 나누어서 생각해 보겠습니다. 저는 1차원 배열로 DP를 잡고 풀었습니다. A 배열은 주어진 계단 점수를 담고 있습니다. N번째 계단이 1번 연속인 경우 N-1번째 계단은 필요 없고, N-2번째 계단의 총점을 합쳐야 합니다. 따라서.. DP[N] = DP[N-2] + A[N] N번째 계단이 2번 연속인 경우 N-1번째 계단은 밟아야 하고, .. 2017. 10. 26. [DP] 백준 2193 이친수 (Pinary Number) BackJoon # 2193 - 이친수 (Pinary Number) https://www.acmicpc.net/problem/2193 대표적인 DP문제입니다. DP[N] 을 N개 자리수에 이친수를 만족하는 경우의 수라고 생각하겠습니다.N자리에 올 수 있는 숫자는 0 OR 1입니다. 각각에 경우에 대해서 생각해 보겠습니다. N자리에 0인 경우 N-1자리에 올 수 있는 숫자는 0 OR 1 둘 다 가능합니다. 따라서 DP[N] = DP[N-1] 이 성립합니다. N자리에 1인 경우 N-1자리에 올 수 있는 숫자는 0 만 가능합니다. 그렇다면 N-2 자리에 올 수 있는 숫자는? 0 OR 1 이 가능합니다. 따라서 . . . DP[N] = DP[N-2] 이 성립합니다. 이제 N자리에 0 이 올수도 1이 올수도 있으.. 2017. 10. 25. 이전 1 다음 반응형
