cyj893

저장소

백준: Class 5 - 2143, 2342, 7579

3 분 소요


</br> 클래스 5 계속
</br>

2143: 두 배열의 합

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

    dp[0] = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        le.push_back(a[i]);
        dp[i] = a[i] + dp[i-1];
    }
    for(int i = 2; i <= n; i++){
        for(int j = i; j <= n; j++){
            le.push_back(dp[j] - dp[j-i]);
        }
    }
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> b[i];
        ri.push_back(b[i]);
        dp[i] = b[i] + dp[i-1];
    }
    for(int i = 2; i <= m; i++){
        for(int j = i; j <= m; j++){
            ri.push_back(dp[j] - dp[j-i]);
        }
    }

    sort(le.begin(), le.end());
    sort(ri.begin(), ri.end());

    int l = 0, r = ri.size()-1;
    long long ans = 0;
    while( l < le.size() && r >= 0 ){
        int sum = le[l] + ri[r];
        if( sum == t ){
            int ll = le[l], rr = ri[r];
            long long cnt1 = 0, cnt2 = 0;
            while( l < le.size() && le[l] == ll ){
                l++;
                cnt1++;
            }
            while( r >= 0 && ri[r] == rr ){
                r--;
                cnt2++;
            }
            ans += cnt1*cnt2;
        }
        else if( sum < t ) l++;
        else r--;
    }
    cout << ans << endl;

전 포스트의 투 포인터 문제(1208: 부분수열의 합 2, https://cyj893.github.io/algorithm/Algorithm15_6/)와 유사한데 더 쉽다 얘를 먼저 풀고 풀었으면 1208도 맞출 수 있었을까
dp에 누적합을 구해 놓고 이를 이용해 le 벡터에 a의 모든 합들을 넣는다(ri도 마찬가지).

ex)
5
3
1 2 3
4
1 2 3 4

le: 1 2 3 3 5 6
ri: 1 2 3 3 4 5 6 7 9 10

그리고 투 포인터 하면 됨
참고로 ans나 cnt나 long long으로 선언하는 게 마음이 편하다
</br>

2342: Dance Dance Revolution

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

int func(int pre, int now){
    if( pre == 0 ) return 2;
    if( pre == now ) return 1;
    if( abs(pre-now) == 2 ) return 4;
    return 3;
}

// in main()
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < ind; k++){
                dp[i][j][k] = 500000;
            }
        }
    }
    dp[0][0][0] = 0;

    for(int i = 1; i < ind; i++){
        int s = steps[i];
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 5; k++){
                if( j == k ) continue;
                for(int p = 0; p < 5; p++){
                    if( k == s ) dp[j][k][i] = min(dp[j][k][i], dp[j][p][i-1] + func(p, steps[i]));
                    if( j == s ) dp[j][k][i] = min(dp[j][k][i], dp[p][k][i-1] + func(p, steps[i]));
                }
            }
        }
    }

    int ans = 500000;
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            ans = min(ans, dp[i][j][ind-1]);
        }
    }
    cout << ans << endl;

dp 문제긴 한데 가능한 경우 그냥 다 저장하면 된다
일단 dp의 맥스를 나올 수 없는 값인 500000으로 다 초기화 한다.
만약 같은 곳이라면 그냥 넘겨서 맥스 값으로 둔다.
만약 오른쪽이 현재 스텝과 같다면, 전 단계의 모든 오른쪽 스텝들에 더한 값 중 min값으로 업데이트 해 준다(왼쪽도 마찬가지).

ex) 백준 예제
1 2 2 4 0


1(1)
500000 2      500000 500000 500000
2      500000 500000 500000 500000
500000 500000 500000 500000 500000
500000 500000 500000 500000 500000
500000 500000 500000 500000 500000

2(2)
500000 500000 5      500000 500000
500000 500000 4      500000 500000
5      4      500000 500000 500000
500000 500000 500000 500000 500000
500000 500000 500000 500000 500000

3(2)
500000 500000 6      500000 500000
500000 500000 5      500000 500000
6      5      500000 500000 500000
500000 500000 500000 500000 500000
500000 500000 500000 500000 500000

4(4)
500000 500000 500000 500000 10
500000 500000 500000 500000 9
500000 500000 500000 500000 8
500000 500000 500000 500000 500000
10     9      8      500000 500000

8


</br>

7579: 앱

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

    int ans = INT_MAX;
    dp[0][c[0]] = a[0];
    if( dp[0][c[0]] >= m ) ans = min(ans, c[0]);
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= 10000; j++){
            if( j >= c[i] )
                dp[i][j] = max(dp[i][j], dp[i-1][j-c[i]] + a[i]);
            dp[i][j] = max(dp[i][j], dp[i-1][j]);
            if( dp[i][j] >= m ) ans = min(ans, j);
        }
    }

    cout << ans << endl;

마음 같아선 dp[101][10000001]로 선언해 버리고 싶지만 그러면 메모리 초과 난다
그래서, dp[101][10001]로 선언한다(비용 기준 100*100)
dp[i][비용] = max(dp[i][비용], dp[i-1][비용 - (현재 앱의 비용)] + 현재 앱의 메모리
즉 dp[i][j]의 값이 메모리이고, j가 출력해야 할 답인 비용이 된다.
</br>

방학이 끝나간다
</br>

댓글남기기

참고