계단오르기

1. 소스 코드

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

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

[완전 탐색]

#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]

#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