[Csacademy] Csacademy Round #27 (Div. 2 only) 이야기

요즘 파이썬과 홈페이지 제작에 관심이 생겨 알고리즘을 소홀히 하고 있다가 시험을 쳤다.

A는 금방 풀긴 했지만, B번이 풀릴 것 같으면서도 풀리지 않았다.

레이팅은 1404(-1)로 마무리 하였다.

A. Backpack Packing :: https://csacademy.com/contest/round-27/#task/backpack-packing

A와 B가방 중 공간이 더 많이 남은곳에 입력으로 들어온 짐을 넣는 과정이다.

이때 남는 짐의 개수를 구하는 문제이다.

조건만 잘 세우면 쉽게 해결이 가능하다.

시간 복잡도는 O(n)에 해결되는 문제이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include <iostream> #include <cstdio>   using namespace std;   int arr[103];   int main() {     int a, b, n;     scanf("%d %d %d", &a, &b, &n);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       int cnt = 0;     for(int i = 0 ; i < n ; i ++)     {         if (a - arr[i] < 0 && b - arr[i] < 0)         {             cnt++;             continue;         }         if (a >= b)             a -= arr[i];         else             b -= arr[i];     }       printf("%d", cnt);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B. Backpack Packing :: https://csacademy.com/contest/round-27/#task/max-even-subarray

B번은 Prefix Sum과 투 포인터의 조합인 줄 알았지만, DP였다.

솔직히 DP일 것이라고는 생각하지도 못했다.

문제는 단순하다. 부분 배열의 합을 구하는 문제인데, 짝수에 대해서만 그 값을 구해준다.

문제 솔루션은 다음과 같았다.

dp[i][0] = dp[i - 1][1] + arr[i]; // i번째까지 짝수 최대 합

dp[i][1] = max(dp[i - 1][0] + arr[i], arr[i]); // i번째까지 홀수 최대 합

간단한 문제였지만, DP라는 개념을 생각하지 못했고, 이 알고리즘은 추후 알고리즘 게시판에 올릴 예정이다.

시간 복잡도는 O(n)에 해결되는 문제이다.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <limits.h>
 
#define INF 1e18+1
 
using namespace std;
 
long long arr[100002];
long long dp[100002][2];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
 
    dp[0][0] = dp[0][1] = -INF;
    long long ans = -INF;
 
    for (int i = 1; i <= n; i++)
    {
        // i번째까지 짝수 최대 합
        dp[i][0] = dp[i - 1][1] + arr[i];
        // i번째까지 홀수 최대 합
        dp[i][1] = max(dp[i - 1][0] + arr[i], arr[i]);
 
        ans = max(ans, dp[i][0]);
    }
 
    printf("%lld", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>