[Sofeteer] 징검다리 - C++

문제

https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

• 소요 시간 : 1시간
• 난이도 : LV 3

접근 방법

 

1. 완전탐색

1. 모든 돌에서 출발해본다.

2. 출발한 돌에서 다음 큰 돌을 모두 방문해본다.  

 

-> 시간복잡도 : O(2^N)

 

..터지는게 당연했다^^

 

2. DP

dp[i] = i 돌까지 도달하는데 제일 많이 밟을 수 있는 징검다리의 수

 

dp[i] = dp[j] + 1 이라고 할 때

 

j의 조건 :

 

1. i보다 작아야 한다. (왼쪽 돌)

2. i번째 돌보다 j번째 돌의 크기가 작아야 한다. 

 

이를 만족하는 j 중에서도 dp[j]가 가장 큰 걸 선택하면 된다. 

 

-> 시간복잡도 : O(N^2)

나의 풀이

1. 완전탐색

#include<iostream>
#define MAX 3000+4

using namespace std;

int N;
int map[MAX];
int answer = 0;

bool isLastBig(int idx) {
    for(int i=idx+1; i<N; i++) {
        if (map[i] > map[idx]) 
            return false;
    }

    return true;
}
void backtracking (int idx, int count) {    

    if (idx == N || isLastBig(idx)) {
        answer = max(answer, count);
        return;
    }

    for(int next=idx+1; next<N; next++) {
        if (map[next] > map[idx]) {
            backtracking(next, count + 1);
        }
    }

    return; 
}

int main(int argc, char** argv)
{
    cin >> N;
    
    for(int i=0; i<N; i++) {
        cin >> map[i];
    }

    for(int i=0; i<N; i++) {
        backtracking(i, 1);
    }

    cout << answer;
    
    return 0;
}

 

결과 : 시간초과

 

2. DP

#include<iostream>
#include<algorithm>

#define MAX 3000+4

using namespace std;

int N;
int map[MAX];
int dp[MAX];

int main(int argc, char** argv)
{
    cin >> N;
    
    for(int i=0; i<N; i++) {
        cin >> map[i];

        // init
        dp[i] = 1;
    }

    // 9000000
    // dp[i] = max(j < i, map[j] < map[i]) dp[j] + 1
    for(int i=1; i<N; i++) {

        int max_j = 0;
        for(int j=0; j<i; j++) {
            if (map[i] > map[j]) {
                max_j = max(dp[j], max_j);
            }
        }

        dp[i] = max_j + 1;
    }

    cout << *max_element(dp, dp+N);
    
    return 0;
}

 

결과 : 정답

정리

DP의 위대함을 다시 꺠우쳤다.. 

백트래킹 시간복잡도 계산하는 법을 다시 유의해야겠다.

LIS 최장 부분 증가 수열로도 풀수 있다고 한다.

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

숙지하고 다시 풀어봐야지~~

참고

https://www.youtube.com/watch?v=egMtFlkH8LQ