백준 | 2579. 계단오르기

 

dfs 사용해서

0	1	2	3	4	5	6
start	10	20	15	25	10	20

 

계단을 이런식으로 입력해놓고

1			2
2	3		3		4
4	4	5	4	5	6
6	6	6	6	6

이렇게 dfs를 실행해보고 싶었슨...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void stairs(vector<int>v, int&ans, int num, int cnt, int i){
    num += v[i];
    // cout << ans << "**" << num << "**" << cnt << "**" << i << "\n"; 흐름파악용
    
    if(i==v.size()) {
        ans = max (ans, num);
        return;
    } // 계단 맨 끝에 가면 종료

    if(i == v.size()-1){
        if(cnt!=2) stairs(v, ans, num, cnt+1, i+1); // 한칸 올라가기
        return; // 맨 끝에 못다다르면 종료
    }

    if(cnt != 2) stairs(v, ans, num, cnt+1, i+1); // 연속 3칸 아닐 때는 1개 오르기 가능
    stairs(v, ans, num, 1, i+2); // 두칸 올라가기
}

int main(){
    int N;
    cin >> N;
    vector <int> v(N+1,0);
    for(int i =1; i<= N; ++i) cin >> v[i];

    int ans = 0;
    stairs(v, ans, 0, 0, 0);
    
    cout << ans;
}

 

그래서 구현한게 이건데 시간초과 나와서 다른 조금 더 효율적인 방법을 고민해보기로

뭔가 이것도 데이터 더하고 하는게 반복되는거같아서

dp로 구현하는걸 문제에서 원하는 것 같음

그래서 dp로 구현하려는데 연달아서 3칸 못올라가는거 때문에 고민...

 

두칸 점프하는거는 dp[i-2]+v[i]로 하면 될거같은데

연달아 올라가는거는 바로 앞에 값 더하면 세칸 연달아가 될 수도 있으니까

무조건 점프+연달아로 실행이 되어야한다는 점을 활용해서

dp[i-3]+v[i-1]+v[i]

이렇게 해서 구현해보면 되지 않을까?

 

일단 해봐.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector <int> v(N+1,0);
    for(int i =1; i<= N; ++i) cin >> v[i];

    vector<int>dp(N+1, 0);
    dp[1] = v[1];
    dp[2] = v[1]+v[2];
    for(int i = 3; i<=N; ++i){
        dp[i] = max(dp[i-2]+v[i], dp[i-3]+v[i-1]+v[i]);
        //두칸 jump해서 온거 vs 연달아온거 비교해서 더 큰 값 저장
        //연달아서 온거는 3칸 연달아오는거 방지 위해 3칸 아래 애랑 비교
    }
    cout << dp[N];
}

 

 역시 바로 성공 ★