AtCoder Beginner Contest 281

A - Count Down

단순 출력문제

let N = Int(readLine()!)!
for i in 0...N { print(N-i) }

B - Sandwich Number

다음 조건을 만족하면 Yes를 출력하고 아니면 No를 출력한다.

첫째자리가 영어 대문자
두번째 ~ 일곱번째가 100000부터 999999 사이의 수
여덟번째 자리가가 영어 대문자

let S: [Character] = Array(readLine()!)

if S.count != 8 {
    print("No")
} else if !S[0].isUppercase {
    print("No")
} else if !((100000...999999) ~= Int(String(S[1...6]))!) {
    print("No")
} else if !S[7].isUppercase {
    print("No")
} else {
    print("Yes")
}

C - Circular Playlist

T가 최대 10^18 개이므로 음악을 처음부터 따라가다보면 무조건 시간초과가 뜬다.
N의 개수가 최대 십만개이므로 O(N)의 시간복잡도로 해결해야하는 문제다.
즉 한번의 1부터 N까지의 순회정도로 끝을 봐야한다.

모든 음악의 합을 저장해놓고 T로 나눈 나머지를 저장하면, 전체를 재생하는 주기들를 지울 수 있다.
(만약 T로 나눈 나머지가 0이면 첫번째 음악을 재생해야함을 보고 출제자에게 매우 고마웠다.)

어쨋든, 이제 한 주기안에 노래가 끝남이 보장되므로
순차적으로 음악을 순회하며 재생이 끊기는 음악을 찾아 출력해주면 되겠다.

let ip = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (N, T) = (ip[0], ip[1])
let A = [0] + readLine()!.split{$0==" "}.map{Int(String($0))!}
let sum = A.reduce(0, +)
var remain = T % sum

for i in 1...N {
    if remain - A[i] >= 0 {
        remain -= A[i]
    } else {
        print(i, remain, separator: " ")
        break
    }
}

D - Max Multiple

C까지는 딱봐도 실버수준이어서 Biginner 는 쉬운가보다^^ 하고 방심하다가 못풀었다.
갑자기 난이도가 뻥튈줄은 몰랐다. 적어도 골드4는 되는 DP문제였다.

f(i, j, k): 0 ~ a[i]번째 까지의 요소들 중 j개 요소를 선택해 더한 나머지가 k인 최대 합 이라고 정의한다.
여기서 내가 막힌 부분은 점화식을 찾기위해 인덱스 i에 대해서
(x + a[i]) % D = 0이되는 x를 찾기 위해 DOG고생을 하고있었다.
내가 수학공부를 너무 안했나.. 하고있었는데, 생각해보니 점화식을 정의할때,

이전 + ☆ = 현재 와 같이 정의하지 않고,
현재 + ♬ = 미래 와 같이 정의하면 간단히 해결되는 문제였다.

때문에 점화식은 다음과같이 정의할 수 있다.

f\left(i+1,\ j+1,\ \left(k+a\left[i+1\right]\right)\%D\right)\ =\ \max _{ }^{ }\left(f\left(i,j,k\right)+a\left[i+1\right],\ 자신\right)

f\left(i+1,\ j,\ k\right)\ =\ \max _{ }^{ }\left(f\left(i,j,k\right),\ 자신\right)

('자신'은 좌항을 의미한다. 다시쓰기 귀찮다.)

저 점화식을 풀면된다.

let ip = readLine()!.split{$0==" "}.map{Int(String($0))!}
let (N, K, D) = (ip[0], ip[1], ip[2])
let a = [0]+readLine()!.split{$0==" "}.map{Int(String($0))!}
var dp = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: -1, count: D), count: K+1), count: N+1)

dp[0][0][0] = 0;

for i in 0..<N {
    for j in 0...K {
        for k in 0..<D {
            if dp[i][j][k] == -1 { continue }
            
            dp[i+1][j][k] = max(dp[i][j][k], dp[i+1][j][k])
            
            if j == K { continue }
            dp[i+1][j+1][(k+a[i+1])%D] = max(dp[i][j][k]+a[i+1], dp[i+1][j+1][(k+a[i+1])%D])
        }
    }
}

print(dp[N][K][0])

E - Least Elements

multiset을 2개를 관리해서 풀 수 있는 문제였다.
multiset L과 R을 만들고
L에는 M개의 원소 중 앞의 K개, R에는 나머지 M-K개로 초기화해준다.

이제 스위핑하며 A[i-M]번째 원소를 L 또는 R에서 삭제해주고,
A[i]번째 원소를 넣어주여야 한다.

유의할점은 K=1, M=1 이라고 할 때,
L에는 1개의 원소, R에는 0개의 원소가 있을것이다.
삭제 연산을 먼저 한다고하면,
L에서 삭제가 되고 L을 1로 유지시키기 위해 R의 첫번째 원소를 넣어주려고하면 런타임에러다.

즉 삭제연산보다 넣는연산을 먼저 해주자.
L에 먼저 넣고, L의 마지막원소를 R에 넣어준다. 그러면
L에는 K개의 원소, M에는 M-K+1개가 존재하게 되며, 갯수들은 항상 1 이상이된다.

이제 삭제연산을 L 또는 R에서 해주고 L은 K, R은 M-K개의 원소를 가지도록 해주면 된다.

( + multiset에서 set.erase(value)는 모든 value를 삭제하고
set.erase(set.find(value))은 한개만 삭제한다고한다... 어제 이것때문에 개고생했는데 ㅠ
하나 배워간다. )


#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tii;

const int MAX = 200005;
int N, M, K, A[MAX];
multiset<int> L;
multiset<int> R;
ll ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> M >> K;
    for (int i=1;i<=N;i++) cin >> A[i];

    for (int i=1; i<=M; i++) {
        L.insert(A[i]), ans += A[i];
        if (L.size() > K) {
            R.insert(*L.rbegin());
            ans -= *L.rbegin();
            L.erase(--L.end());
        }
    }

    cout << ans << ' ';
    for (int i=M+1; i<=N; i++) {
        int w = A[i-M];
        L.insert(A[i]), ans += A[i];

        ans -= *L.rbegin();
        R.insert(*L.rbegin());
        L.erase(--L.end());

        if (w <= *L.rbegin()) {
            ans -= w;
            L.erase(L.find(w));
            ans += *R.begin();
            L.insert(*R.begin());
            R.erase(R.begin());
        } else {
            R.erase(R.find(w));
        }

        cout << ans << ' ';
    }

    return 0;
}

앵간하면 swift로 하려고했는데 도저히 안되겠어서 C++ 썼습니다.

댓글