dldyou

어느덧 아무것도 할 줄 모르는 4학년이 되고 졸업유예를 한 상태로 마지막이 될 ICPC를 도전해보기로 했다. 거의 3년은 알고리즘을 쉬었기에 기존의 모든 알고리즘 지식을 잃어버린 상태로 맨 처음부터 시작한다는 마음가짐으로 공부를 시작했다. 블로그도 2년만에 들어와봤는데, 공부한 것을 정리할 겸 다시 기록해보고자 한다.

1주차

우선 현재 상태를 점검하고자 S3-G3 난이도의 문제들을 랜덤으로 돌리면서 실수는 많지만 그래도 빠르게 빠르게 문제를 풀어 1주차가 끝나는 시점인 6-7일차에 골랜디를 시작할 수 있게 되었다.

2주차

1주차에 자체 점검을 가진 이후로 골랜디를 진행하고 있던 와중 실수가 너무 많다고 느껴 9일차부터 구현 문제에 한해서 골랜디를 진행 중이다. 아래 문제는 9일차 밤 ~ 10일차에 진행했던 구현 문제들이다.

+ 02, 03 게시글을 작성하는 도중에 백준 서비스 종료 소식을 듣고, 출제하였던 대회 문제들을 QOJ로 옮기는 등의 작업을 진행하였다. 빠르게 플랜디, 다이아 일부 문제 해결까지 실력 복구를 해가던 와중 이렇게 되어 다시 한동안 알고리즘 문제를 풀지 않고 있지만 백준이 돌아온다고 하니 기다려본다. 돌아오기 전까지는 코포 virtual이라도 시간 날 때마다 돌려야겠다.

1089. 스타트링크 타워

[문제] [코드]

일일이 순환하며 숫자를 표현 가능한지 확인할 수 있지만, 비트마스팅을 통해 포함 관계를 구하는 것이 용이하도록 전처리를 진행해주었다. 평균은 모든 경우의 수를 모두 더하는 것은 오래 걸리니 일의 자리부터 나올 수 있는 숫자들의 합을 그 개수로 나눈 후, $10^N$꼴을 곱하여 모두 더해주는 것으로 구할 수 있었다.

16434. 드래곤 앤 던전

[문제] [코드]

체력이 H인 적을 죽이기 위해 공격력이 A인 대상이 공격해야 하는 횟수는 $\lceil \frac{H}{A} \rceil$이 된다. 용사가 먼저 공격을 진행하는 것을 유의한다면 방을 탐색하는 코드는 문제 없이 해결할 수 있다. 나머지는 Pharametric Search를 통해 최대 체력이 H인 경우 용을 잡을 수 있는가? 를 확인하면 된다.

20056. 마법사 상어와 파이어볼

[문제] [코드]

파이어볼을 구조체로 관리하며 그대로 구현해주면 쉽게 풀 수 있었다.

10836. 여왕벌

[문제] [코드]

$(row, col - 1)$, $(row - 1, col - 1)$, $(row - 1, col)$의 모든 애벌레가 성장해야 $(row, col)$의 애벌레가 성장하므로 제일 왼쪽 열과 제일 위쪽 행의 성장만으로 $N$일차의 모든 애벌레의 크기를 구할 수 있다.

즉, 매번 모든 애벌레의 성장을 갱신하는 것이 아닌 마지막 한 번만 갱신해주면 된다.

17779. 게리맨더링 2

[문제] [코드]

5번 선거구 영역을 채운 후 나머지 선거구를 채워주면 된다. 1, 2, 3, 4번 선거구를 직사각형 모양으로 덮으려고 했다가 겹치는 것을 고려하지 않아 틀렸었다.

21609. 상어 중학교

[문제] [코드]

무지개 블록 탐색과 제거할 블록 그룹의 우선순위, 검은색 블록만 유의하며 작성해주면 된다.

34878. Magic Door

[문제] [코드]

위의 문제와 마찬가지로 우선순위를 잘 고려해서 작성해주면 된다.

우하단 / 좌하단 대각선 누적합을 각각 진행해주고, (x, y)에서 변의 길이가 k인 형태에서의 아름다운 정도를 구해서 답을 갱신해주면 된다. $O(N^3)$으로 해결 가능하다.

int N, A[MAXN][MAXN], B[MAXN][MAXN];

int main(void) {
    fastio;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> A[i][j];
            B[i][j] += B[i - 1][j + 1] + A[i][j];   // B 좌하단 대각선 누적합 
            A[i][j] += A[i - 1][j - 1];             // A 우하단 대각선 누적합 
        }
    }

    int ans = -INF;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k <= N - max(i, j); k++) {
                int x1 = j, x2 = j + k;
                int y1 = i, y2 = i + k;
                int beautiful = (A[y2][x2] - A[y1 - 1][x1 - 1]) 
                                - (B[y2][x1] - B[y1 - 1][x2 + 1]);
                ans = max(ans, beautiful);
            }
        }
    }
    cout << ans;
    return 0;
}

1. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.

2. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.

3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다.

위 조건에 따라 그대로 구현해주면 되는 시뮬레이션 문제이다. 최근에 나온 과제를 먼저 해야하므로 스택을 사용해서 구현해주자.

int N;
stack<pair<int, int>> s;
int main(void) {
    fastio;
    cin >> N;
    int score = 0;
    for (int i = 1; i <= N; i++) {
        int isExist, A, T;
        cin >> isExist;
        if (isExist) { // 해당 시간에 과제가 존재
            cin >> A >> T;
            s.push({ A, T }); // 스택에 과제 추가
        }
        if (!s.empty()) { // 해야하는 과제가 남아있는가?
            if (--s.top().ss == 0) { // 최근 과제의 남은 시간을 감소
                score += s.top().ff; // 과제를 다 했으면 점수 추가
                s.pop(); // 그리고, 과제를 제거
            }
        }
    }
    cout << score;
    return 0;
}

수열 $S$에서 $K$개의 원소를 임의로 삭제하였을 때, 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.

• 수열에서 필요한 정보는 홀짝이니, $S[i] = S[i]\ \&\ 1$로 홀수면 1, 짝수면 0으로 $S$를 초기화해주자.
• 일정 범위에서 범위를 늘리면 포함되는 홀수, 짝수는 같거나 증가한다. 줄이면 같거나 감소한다.
• 나머지는 투포인터를 이용하여 개수를 세어주면 된다.

int N, K, S[MAXN];
int main(void) {
    fastio;
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        cin >> S[i], S[i] = (S[i] & 1);
    int s = 1, e = 1;
    int cnt = S[1], ans = !S[1], tmp = !S[1];
    while (s <= e && e < N) {
        if (cnt <= K) {
            e++;
            cnt += S[e];
            tmp += !S[e];
            ans = max(ans, tmp);
        }
        while (cnt > K) {
            cnt -= S[s];
            tmp -= !S[s];
            s++;
        }
    }
    cout << ans;
    return 0;
}

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

규칙에 따라 섞인 수열의 맨 처음 형태를 구하면 된다.

$P_i$에서 $i=D_i$인 경우 $S_i$가 된다.

즉, $P[D[i]]=S[i]$이다. 이를 $K$번 반복해주면 된다. $NK\leq 10^7$이기에 전부 돌려봐도 해결 가능하다.

int N, K, S[MAXN], D[MAXN], P[MAXN];
int main(void) {
    fastio;
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> S[i];
    for (int i = 1; i <= N; i++) cin >> D[i];
    while (K--) {
        for (int i = 1; i <= N; i++) P[D[i]] = S[i];
        for (int i = 1; i <= N; i++) S[i] = P[i];
    }
    for (int i = 1; i <= N; i++) cout << P[i] << ' ';
    return 0;
}

3개의 제품을 한 번에 사면 그 중 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 된다. 만약, 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 한다. 이때, 최소비용으로 모든 제품을 구입하면 된다.

결국, 무료로 지불하는 금액을 최대화하면 최소비용으로 모든 제품을 구입하는 것과 같다.

최대화하려면 비싼 순서대로 무료로 구입하면 된다. 하지만 3개를 묶어서 그 중 가장 싼 제품만 무료로 구입할 수 있기에, 비싼 순서대로 나열했을 때 3의 배수에 속해있는 것을 제외한 모든 제품의 가격을 더해주면 된다. 

반대로 생각하면 모든 가격에서 3의 배수에 속해있는 가격을 제외하면 된다.

long long N, C[MAXN], ans;
int main(void) {
    fastio;
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> C[i], ans += C[i];
    sort(C, C + N, greater<long long>());
    for (int i = 2; i < N; i += 3)
        ans -= C[i];
    cout << ans;
    return 0;
}

돌 $N$개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람이 누구인지를 구하여라. 게임은 상근이가 먼저 시작한다.

돌이 1, 3, 4개인 경우는 상근이가 돌을 1개 가져가면 상근이가 승리한다.

나머지도 채워보자.

2개인 경우는 1 - 1개 순서로 가져가 창영이가 승리한다.

5개인 경우는 3 - 1 - 1개 순서로 가져가 상근이가 승리한다. 

6개인 경우는 4 - 1 - 1개 순서로 가져가 상근이가 승리한다.

7개인 경우는 1 - 4 - 1 - 1개 순서로 가져가 상근이가 승리한다.

...

이런 식으로 게임이 진행될 것이다. 

6개인 경우에서 1개를 가져가는 것은 턴이 바뀐 상태로 5개인 게임판에서 게임을 다시 진행하는 것과 같다.

만약, 6개인 게임판에서 돌을 1개 가져가는 행동만 할 수 있는 경우, 5개인 게임판으로만 갈 수 있고 5개인 게임판에서 A가 승리하는 결과라면 6개인 게임판에서는 A는 반드시 패배한다. 

지금 위의 문제에서 나온 형태는 1, 3, 4개가 줄어든 게임판으로 갈 수 있다. 해당 게임판으로 갔을 때의 선공이 지는 경우가 하나라도 존재하면 현재 게임판에서는 선공이 승리한다. 

1개 게임판은 선공이 승리한다.

2개 게임판은 1개 게임판으로만 이동 가능하다. 선공이 승리하는 경우만 있으므로 2개 게임판은 선공이 패배한다.

3개 게임판은 0, 2개 게임판으로 이동 가능하다. 0개 게임판과 2개 게임판 모두 선공이 패배하는 게임판이다. 즉, 3개 게임판은 선공이 승리한다.

4개 게임판은 0, 1, 3개 게임판으로 이동 가능하다. 0개 게임판은 선공이 패배하는 게임판이다. 플레이어는 완벽하게 플레이하기에 이기려고 한다. 즉, 0개 게임판으로 이동한다. 4개 게임판은 선공이 승리하는 게임판이다. 

... 이런식으로 채워나가면 된다. 

결국, 7로 나눈 나머지가 0 또는 2인 경우를 제외하고는 상근이가 승리한다.

각각의 작업마다 걸리는 시간이 다른 것을 $N$개를 모두 완료하기 위해 필요한 최소 시간을 구하는 문제이다. 작업들 사이에는 선행 관계가 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 하는 작업들이 있다. 

'선행 관계' 대놓고 위상 정렬 문제이다. 

위상 정렬(topological sort)은 비순환 방향 그래프(DAG)에서 각 정점들이 가지는 위상에 따라 순서대로 나열하는 것을 의미한다. 선수 과목, 게임에서의 테크 등을 생각하면 편할 것이다. 

각각의 건물이 지어지는 시간을 구한 다음 최댓값을 출력하면 그것이 모든 건물을 짓는데 걸리는 최소 시간이다. 

int N, cost[MAXN], in_degree[MAXN], dp[MAXN];
vector<int> v[MAXN];
queue<int> q;

int main(void) {
    fastio;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> cost[i] >> in_degree[i]; dp[i] = cost[i];
        for (int j = 1; j <= in_degree[i]; j++) {
            int prev; cin >> prev;
            v[prev].push_back(i);
        }
        if (in_degree[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (int next : v[cur]) {
            in_degree[next]--;
            dp[next] = max(dp[next], dp[cur] + cost[next]);
            if (in_degree[next] == 0)
                q.push(next);
        }
    }

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

정수 $X$가 주어졌을 때, $X$와 구성이 같으면서 $X$보다 큰 수 중 가장 작은 수를 출력하는 문제이다. $X$는 최대 6자리 수이므로 나올 수 있는 수는 최대 $6!$개이다. 모두 탐색을 해도 충분한 시간이다. 

맨 처음 수를 저장해놓고, 숫자를 정렬한다. 그 후에는 그 다음으로 나올 수열을 찾아보며 해당 수열이 맨 처음 수보다 큰지 확인을 해가면서 탐색을 진행하면 된다. 만약, 끝까지 큰 값이 없었다면(내림차순 정렬값이 맨 처음 수였다면) 0을 출력한다.

string s;
int n;

bool vst[7];
void solve(string str) {
    if (str.length() == s.length()) {
        if (stoi(str) > n) {
            cout << str << '\n';
            exit(0);
        }
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        if (!vst[i]) {
            vst[i] = true;
            solve(str + s[i]);
            vst[i] = false;
        }
    }
}

int main(void) {
    fastio;
    cin >> s;
    n = stoi(s);
    sort(all(s));
    solve("");
    cout << 0;
    return 0;
}

`next_permutation`을 이용하면 간단해진다.

int main(void) {
    fastio;
    string s; cin >> s;
    if (next_permutation(all(s))) cout << s;
    else cout << 0;
    return 0;
}

$N$개의 길이 중 3개를 선택하여 삼각형을 만들었을 때, 세 변의 길이의 합의 최댓값을 구하는 문제이다. 

그리디하게 접근해 보자. 세 변의 길이의 합을 최대로 만들려면 당연히 길이들 중 최대한 긴 것을 선택해야 한다. 그렇다면 정렬을 먼저 해보자. 

가장 큰 3개를 봤을 때, 삼각형이 안 되면 어떤 길이를 선택해야 할까?

XXXXXXXOOO에서 XXXXXXOXOO 이런 식으로 선택을 해야 할까? 

삼각형을 이루는 세 변의 길이의 조건을 생각해 보자.

'가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 한다.'

가장 긴 3개를 골랐을 때, 삼각형이 안 된다면 가장 긴 길이를 유지한 채로 다른 변을 더 짧은 길이를 선택하는 것은 삼각형에서 멀어지는 길이다. 위의 상황과 같이 가장 긴 길이를 기준으로 바로 다음 2개의 변으로 삼각형을 만들지 못한다면, 해당하는 가장 긴 길이의 변으로는 삼각형을 만들지 못한다.

즉, 연속되는 3개의 변만 차례로 확인하면 된다.

int N; 
vector<int> v;

int main(void) {
    fastio;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x; cin >> x;
        v.push_back(x);        
    }
    sort(all(v), greater<int>());

    for (int i = 0; i < N - 2; i++) {
        if (v[i] < v[i + 1] + v[i + 2]) {
            cout << v[i] + v[i + 1] + v[i + 2] << "\n";
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}