백준: Class 4 - 11444, 11054, 11779

</br> 클래스 4 마지막이구나
</br>

11444: 피보나치 수 6

https://www.acmicpc.net/problem/11444

입력이 1000000000000000000이다. 루트하면 1000000000 즉 10억인데, 그 말은 O(N)도 아니고 O(logN)에 풀라는 뜻이겠다.

방법 1.

    if( n == 0 ) cout << 0 << '\n';
    else if( n == 1 ) cout << 1 << '\n';
    else{
        int a, b, c;
        a = 0; b = 1;
        for(long long i = 2; i <= n; i++){
            c = a + b;
            c %= 1000000007;
            a = b;
            b = c;
        }
        cout << b << '\n';
    }

기본적인 피보나치 얻기
계속 더해 나가 주면 된다

물론 시간 초과다
</br>

방법 2.

Fn = 1Fn-1 + 1Fn-2
   = 1(Fn-2 + Fn-3) + 1Fn-2
   = 2Fn-2 + Fn-3
   = 2(Fn-3 + Fn-4) + 1Fn-3
   = 3Fn-3 + 2Fn-4
   = 3(Fn-4 + Fn-5) + 2Fn-4
   = 5Fn-4 + 3Fn-5
   = 5(Fn-5 + Fn-6) + 3Fn-5
   = 8Fn-5 + 5Fn-6
   = 8(Fn-6 + Fn-7) + 5Fn-6
   = 13Fn-6 + 8Fn-7

   = Fa+1 * Fn-a + Fa * Fn-a-1

b = n/2
if( n이 짝수 )
   = Fb+1 * Fb + Fb * Fb-1
if( n이 홀수 )
   = Fb+1 * Fb+1 + Fb * Fb

그래서 전개하다 보니 이런 식이 나왔다!!
아하~ 대충 n을 반띵 비슷하게 할 수 있으니까 괜찮지 않을까

long long fibo(int d){
    if( d == 0 ) return 0;
    if( d == 1 ) return 1;

    int a = d/2;
    long long fam1, fa, fap1;
    fam1 = fibo(a-1) % 1000000007;
    fa = fibo(a) % 1000000007;
    fap1 = (fa + fam1) % 1000000007;

    if( d % 2 )
        return (fap1*fap1) % 1000000007 + (fa*fa) % 1000000007;
    return (fap1*fa) % 1000000007 + (fa*fam1) % 1000000007;
}

그럼 이렇게 하면 될까

안 된다
재귀라서 하나 하나 다 구한다.
그래서 맵에다 저장하고 할까? 했는데
맵도 용량 초과 나고 난리난다
</br>

방법 3.

    if( n == 0 ) cout << 0 << '\n';
    else if( n == 1 ) cout << 1 << '\n';
    else{
        int a, b, c;
        a = 0; b = 1;
        for(long long i = 2; i <= n; i++){
            c = a + b;
            c %= 1000000007;
            a = b;
            b = c;
        }
        cout << b << '\n';
    }

그럼 대체 뭐지~~ 해서 검색 결과
https://jow1025.tistory.com/101
피보나치를 행렬의 제곱으로 표현할 수 있고, 행렬의 제곱을 분할 정복하면 된단다

몰랐으니 어쩔 수 없지…
이제 알았으니 됐다
</br>

11054: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054

    a[0] = 0;
    a[n+1] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < i; j++){
            if( a[i] > a[j] ) dp1[i] = max(dp1[i], dp1[j]+1);
        }
    }
    for(int i = n; i > 0; i--){
        for(int j = i+1; j <= n+1; j++){
            if( a[i] > a[j] ) dp2[i] = max(dp2[i], dp2[j]+1);
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, dp1[i] + dp2[i]);
    }
    cout << ans-1 << endl;

간만에 또 쉬운 게 나와 줬군
이전 포스트인 ‘11053: 가장 긴 증가하는 부분 수열(https://cyj893.github.io/algorithm/Algorithm15_2/)’과 비슷하다
dp1은 증가하는 수열의 최댓값, dp2는 그 반대로 최댓값을 저장하고, 그 합이 제일 큰 곳을 고르면 된다.
참고로 dp1과 dp2가 중복 1이 되므로 답은 빼기 1 해준다

ex) 백준 예제
10
1 5 2 1 4 3 4 5 2 1

dp1: 1 2 2 1 3 3 4 5 2 1
dp2: 1 5 2 1 4 3 3 3 2 1
sum: 2 7 4 2 7 6 7 8 4 2

</br>

11779: 최소비용 구하기 2

https://www.acmicpc.net/problem/11779

    for(int i = 1; i <= n; i++){
        dist[i] = 100000001;
    }
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push(make_pair(0, s));
    dist[s] = 0;
    while( pq.size() ){
        int w = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        if( w > dist[now] ) continue;

        for(int i = 0; i < graph[now].size(); i++){
            int nw = graph[now][i].first;
            int nx = graph[now][i].second;
            if( dist[nx] > w + nw ){
                dist[nx] = w + nw;
                pq.push(make_pair(dist[nx], nx));
                path[nx] = now;
            }
        }
    }

    cout << dist[e] << endl;

    stack<int> st;
    st.push(e);
    int now = e;
    while( now != s ){
        st.push(path[now]);
        now = path[now];
    }

    cout << st.size() << endl;
    while( st.size() ){
        cout << st.top() << ' ';
        st.pop();
    }
    cout <<endl;

다익스트라인데, 갱신된 경로도 알아야 하는 문제다.
따라서 path[] 배열을 따로 만들고, 거기다 갱신된 지점을 기록해 두었다.
이를 되추적하면 길을 알 수 있겠지~~

ex)
5
8
1 2 7
1 3 3
1 4 1
1 5 10
2 5 2
3 4 5
3 2 1
4 5 8
1 5

now  w
1    0
dist: 0 7 3 1 10
path: 0 1 1 1 1

4    1
dist: 0 7 3 1 9
path: 0 1 1 1 4

3    3
dist: 0 4 3 1 9
path: 0 3 1 1 4

2    4
dist: 0 4 3 1 6
path: 0 3 1 1 2

5    6
dist: 0 4 3 1 6
path: 0 3 1 1 2

2    7
5    9
5    10

ans
6
4
1 3 2 5

</br>

---

클래스 4가 끝났다~~
방학 전까지 클래스 5도 끝내야지
오늘은 8월 19일
</br>