계단오르기

1. 소스 코드

백준 https://www.acmicpc.net/problem/2579 문제 정리. 

아래 코드는 완전 탐색으로 구현해 보았다. 완전 탐색도 조건이 계단 오르기 전과 오른 후에 연속해서 한 계단씩 오르는 조건이 달라서 코드가 지저분해졌다. 맞게 구현했는지도 솔직히 모르겠다. 두 가지 가능성에 대해서 TC로 돌려봤는데 생각하는데로 나오기는 했는데.

[완전 탐색]

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

#include <iostream>   int max = -1; bool first = true;   #ifdef TEST_BY_TC int N = 6; int data[302] = {0, 10, 20, 15, 25, 10, 20}; //int data[302] = {0, 5, 30, 30, 5, 20, 30}; #else int data[302]; int N; #endif   void f(int d, int c, int v) {       //std::printf("d = %d, c = %d v = %d, data = %d \n", d, c, v, data[d]);           if(d == N+1)     {         if(max < v)         {             max = v;         }         std::cout << "arrived ." << std::endl;         return;     }        if(d > N+1)     {         std::cout << "out of range" << std::endl;         return;     }           // 계단을 오르기 전의 경우 대응     if(c == 3 && first == true)     {        std::cout << "continuous _1 ." << std::endl;         first = false;        return;            }       // 계단을 오른 후에 경우 대응     if(c == 2 && first == false)     {        std::cout << "continuous 1 ." << std::endl;        return;            }        f(d+1, c+1, v + data[d]);     f(d+2, 0, v + data[d]); }   int main() { #ifndef TEST_BY_TC     int n;     std::cin >> n;     N = n+1;       for(int i = 1; i < N; i++)     {         std::cin >> data[i];     } #endif        f(0, 0, 0);       std::cout << "max : " << max << std::endl;     return 0; }

2. DP 코드

처음에는 완전 탐색에서 더 탐색하지 않아도 되는 가지를 쳐 낼려고 했는데, 아무리 노력해도 되지 않아서 풀이를 찾기 시작했다. 풀이나 코드를 보고도 이해가 잘 안되었는데, 딱 이해를 할 수 있도록 정리하신 분이 있다.

따라서 아래 링크를 걸어 둔다.

[DP Code]

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include <iostream>   int stair[301]; int dp[301];   int main() {     int N;       std::cin >> N;       for(int i = 0; i < N; i++)     {         std::cin >> stair[i];     }       dp[0] = stair[0];     dp[1] = std::max(stair[0] + stair[1], stair[1]);     dp[2] = std::max(stair[0] + stair[2], stair[1] + stair[2]);       for(int i = 3; i < N; i++)     {         dp[i] = std::max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]);     }       std::cout << dp[N - 1] << std::endl;       return 0; }

[출처] http://kwanghyuk.tistory.com/4