aoi-aoba.log

[코드포스] 넌 Div2를 너무 쉽게 봤어: Codeforces Round 1087 (Div. 2)

Sun, 22 Mar 2026 01:09:24 GMT

들어가며

개강하고 나서 코드를 짤 일이 많이 없었다. 그냥 매일매일 최대한 시간 날 때 백준 하나 푸는 정도. 그래서 주말에 시간이 되는 김에 조금 피곤하긴 하겠지만 코포를 하나 해보자 하는 생각이 들었고, 마침 시간이 되는 가장 가까운 Codeforces Round 1087을 풀어보기로 했다. 물론 나는 Div.3 이하도 제대로 다 풀지 못하지만 Div.2도 풀어보고 싶다는 생각이 들어 풀었고... 어제의 나 자신의 판단 미스라고 생각한다.

A. Flip Flops

2209A : 문제 링크
코드포스 Div.2는 시작부터 이렇게 다른가? / 16

문제 자체는 크게 어렵지는 않았지만 영어 이슈가 있었다... $n$마리의 몬스터는 각각 $a_i$만큼의 전투력을 가지고, OtterZ는 $c$만큼의 전투력과 $k$개의 슬리퍼를 가지고 있다. OtterZ는 다음과 같은 행동을 한다.

$i$번째 몬스터를 잡을 수 있는 공격력이면($a_i \le c$) 몬스터를 잡고 OtterZ의 공격력은 $c+a_i$가 된다.
살아있는 몬스터 $i$에게 슬리퍼를 던지면 슬리퍼는 망가지고 몬스터가 화가 나서 몬스터의 공격력이 $a_i + 1$이 된다.

테케로 이때 한 줄에 $n$, $c$, $k$와 몬스터들의 공격력 수열이 주어지면 가능한 가장 높은 공격력을 출력하는 문제이다.

그러니까, 공격 횟수(슬리퍼)를 최대한 효율적으로 사용해서 몬스터를 화나게 만들며 내가 잡을 수 있는 한도 내에서 올린 다음 잡으면 된다.

이 한도라는 것은 결국 두 가지 케이스밖에 되지 않는다.

$a_i + k$가 $c$보다 너무 낮은 경우 공격력이 100이고 몬스터 공격력은 11, 슬리퍼가 9라고 해보자. 그러면 슬리퍼를 가지고 다 때려박아도 공격력 20으로 잡을 수 있다.
$a_i + k$가 $c$보다 커지는 경우 공격력이 8이고 몬스터는 7, 슬리퍼가 3이라 해보자. 그러면 아무리 슬리퍼를 던져 화나게 만들어도 8 이상을 만들 수 없다 (못 잡으니까). 그러니까 $c-a_i$ 만큼의 슬리퍼를 던지고 잡을 수 있다.

따라서, 던질 수 있는 최대 횟수인 $\text{min}(c-a_i, k)$에 대해서 매번 자기 자신보다 공격력이 낮은 몬스터를 잡는 방식으로 그리디하게 풀이할 수 있다는 것을 알 수 있다. 어차피 자기 자신 이하의 공격력이면 다 잡을 수 있으니 굳이 수열을 그대로 쓰지 말고 오름차순 정렬해서 어느 시점에서 못 잡으면 그냥 끝내버리면 된다.

그래서 던지는 횟수(throw_count, t_cnt)를 min()으로 구하고 몬스터를 잡아서 c를 업데이트해주고 k의 횟수를 줄여주면 되며, 정렬되어 있는 배열을 돌면서 c보다 큰 시점이 오면 바로 for 루프를 빠져나가면 된다.

    for (int i = 0; i < n; i++) {
        if (a[i] <= c) {
            ll t_cnt = min(k, c - a[i]);
            c += (a[i] + t_cnt);
            k -= t_cnt;
        } else break;
    }

이 코드 빼면 사실 더 설명할 건 없다. 주요 알고리즘이 이게 전부다!

B. Array

2209B : 문제 링크
수직선에서의 거리 개념을 다루는 수학 문제...지만 사실 생각할 건 그렇게 많지 않다? / 25

처음에 수식이 있어서 '아 이거 좀 어렵겠는걸' 하다가 오잉, 하고 그냥 냅다 풀었는데 맞아버린 문제다.

길이 $n$인 정수 배열 $a$에서의 각 인덱스 $i$에 대하여 다음 조건을 만족하는 $j$의 최대 개수를 구하는 것이 목표인데, 조건이란 $j>i$이면서 $|a_i-k|>|a_j-k|$여야 한다. 그러니까, 어떤 정수 $k$를 적절히 골라서 이 $k$까지의 거리가 $a_i$와의 거리보다 짧게 만드는 $a_j$들을 최대한 많이 찾아야 하는 문제인 것이다.

그러면 수직선 상에서 생각해보자. 문제에서 준 식은 사실상 값 $k$가 $a_i$보다 $a_j$에 더 가깝다는 의미다. 임의의 두 수 $x$와 $y$가 있다고 할 때, 어떤 점 $k$가 $x$보다 $y$에 더 가까우려면 어떤 $k$를 잡아야 하는가? 당연하지만, 둘의 중점을 기준으로 $y$쪽에 좀 더 편향되게 위치하면 된다.

즉,

$a_i < a_j$라면 $k$가 둘의 평균인 $m$보다 커야 $a_j$와의 거리가 더 작다.
$a_i > a_j$라면 $k$가 둘의 평균인 $m$보다 작아야 $a_j$와의 거리가 더 작다.
$a_i = a_j$라면 $k$를 어떻게 잡더라도 거리가 같아서 조건을 만족할 수 없다.

그렇기에 결국 특정 $k$에 대하여 조건을 만족하는 $j$ 개수가 최대가 되려고 한다면 각 $i$에 대해 이런 발상을 해볼 수 있다.

$k$를 아주 큰 양수 $p$로 만들어보자. ($k \approx \infin$) 그러면 $a_i < a_j$인 모든 $j$가 조건을 만족하게 되고, 이때의 답은 $i$번 인덱스보다 뒤에 있는 수열의 수들 중 $a_i$보다 값이 큰 것들의 개수가 된다.
$k$를 아주 작은 음수 $q$로 만들어보자. ($k \approx -\infin$) 그러면 $a_i > a_j$인 모든 $j$가 조건을 만족하게 되고, 이때의 답은 $i$번 인덱스보다 뒤에 있는 수열의 수들 중 $a_i$보다 값이 작은 것들의 개수가 된다.

만약 굳이 중간의 어중간한 값으로 잡게 된다면 일부는 만족하지만 일부는 만족하지 못하는 경우가 손실을 야기한다. 즉, 한쪽으로 확실하게 그룹을 전부 가져가는 극단적인 $k$값이 항상 최댓값 후보가 된다.

따라서, 자신 이후에 대하여 le에는 자기보다 작은 값을, gr에는 자기보다 큰 값의 개수를 세어 둘 중 더 큰 것을 출력해주면 되는 간단한 방식을 사용할 수 있다. $N$의 크기가 5000 이하기 때문에 $O(n^2)$으로 풀어도 문제가 없다.

    for (int i = 0; i < n; i++) {
        int le = 0, gr = 0;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[i]) le++;
            else if (a[j] > a[i]) gr++;
        }
        cout << max(le, gr) << (i == n - 1 ? "" : " ");
    }

C. Find the Zero

문제 링크
인터렉티브 문제를 제대로 풀어본 경험이 없던 것도 문제였지만, 문제에 대한 확실한 방식을 찾아내지 못한 것도 문제였다. / 미해결, -2 / upsolve 완료

인터렉티브 문제다. 어떤 배열이 있는데 이 배열은 전체 $2n$ 길이로 되어 있으며 0의 개수가 $n$, 1부터 n까지의 개수가 각각 1개씩 있어서 총 $n$개가 있게 된다. 이런 임의의 배열에 대하여 우리는 $n+1$번의 쿼리 이내에 0의 위치를 찾아야 한다.

할 수 있는 상호작용은 다음과 같다.

? i j를 통해 서로 다른 두 정수 i와 j를 인덱스로 하는 배열의 값이 서로 같은지 다른지를 물어볼 수 있다.
- 대답은 같을 때 1, 다를 때 0이 돌아온다.
- $n+1$번 쿼리를 넘어갔거나 올바르지 않은 쿼리를 만들면 -1을 응답한다.
! k를 통해 답을 제출할 수 있다.
- 그 이후 다음 테스트 케이스를 주거나 마지막 테스트 케이스인 경우에 종료한다.
이 채점기는 적응하는(adaptive) 채점기이다.

아이디어를 생각하는 데 제대로 떠오르지 않았던 것도 있지만, 여러모로 운에 기대는 방식을 선택했던 게 오답의 원인이었던 것 같다. 그래서 결국 대회가 더 끝나기도 전에 너무 피곤한 것도 있고 계속 틀리다가 포기했는데, 아침에 일어나서 생각해보고 업솔브를 완료했다.

일단 상호작용에 대한 결과를 생각해볼 수 있다.

만약 0이라는 결과가 돌아왔다면 알 수 있는 것은 특별히 없다. 두 수가 서로 다르다는 것은 0과 어떤 양의 정수일 수도 있고, 서로 다른 양의 정수일 수도 있다. 서로 0과 0이 아니라는 것만 알 수 있기 때문에 확실하게 '이들은 0이 아니다'라고 배제할 수 있는 경우는 아니다.
만약 1이라는 결과가 돌아왔다면 서로 같은 값을 가질 경우는 무조건 0과 0으로 같을 경우이므로 비교했던 두 인덱스 중 하나를 출력하면 정답을 받을 수 있다.

그러면 이것을 최대한 적게 비교해야 한다는 것인데, 내가 이전에 틀렸던 것은 나중에 얘기하고 답에 대한 이야기를 먼저 해보자.

먼저, 수들을 각각 두 개씩 나눠 구역을 만들자. 그러면

(1, 2) (3, 4) (5, 6) (7, 8) (9, 10) ...

과 같은 형태로 나눠질 것이다(1-based index). 이랬을 때 $n$개의 쿼리로 전부 검색을 해볼 수도 있다. 그러면 운이 좋다면 중간에 (0, 0)이 있을 수도 있겠다. 하지만 그건 만약 최악의 상황으로 치닫았을 때가 문제가 된다.

가령 저 모든 구역을 돌아서 체크했을 때 (0, 0)이 없다면? 축하한다! 이제 한 번의 쿼리만이 남았고, 찍으면 된다! 적어도 (1, 2) (3, 4)중에 찾아봐야 할 텐데, 그게 가능하겠는가? 아니, 그럴 리 없다. 경우의 수가 벌써 (1, 3) (1, 4) (2, 3) (2, 4)인데 이들 중 하나를 검색해서 확실한 0의 위치를 어떻게 얻겠는가. ~~내가 틀린 이유가 이 부분을 항상 간과해서 운에 머물렀기 때문이다~~

그러면 우리는 4개의 문자에 대해서 확실한 답을 얻기 위해 최소 3개의 쿼리가 필요하다는 것을 알 수 있다. 이러면 문제를 해결할 방법을 찾을 수 있다.

(1, 2)와 (3, 4)를 제외한 모든 $n-2$개의 집합들을 각각 모두 검색한다. 탐색하다가 (0, 0)이 나오면 운이 좋은 것이고 그들 중 하나를 출력하면 된다. 하지만 우리는 최악의 경우를 상정하려고 한다.

최악의 경우로 $n-2$개 집합에 대해 모두 (0, 0)이 나오지 않았다는 것은 $(a, b)$ 혹은 $(a, 0)$인 상태가 된다는 것을 말한다. 확실한 건 $2n$개 수 중에서 $n$개가 0인데...

$n-2$개 집합에 대해 모두 $(a, 0)$이라면 (1, 2)와 (3, 4) 두 집합에 대하여 0 두 개가 존재한다.
$n-3$개 집합에 대해 $(a, 0)$이고 하나가 $(a, b)$라면 (1, 2)와 (3, 4) 두 집합에 대해 0이 세 개 존재한다.
$n-4$개 집합에 대해 $(a, 0)$이면 둘은 $(a, b)$가 되고 (1, 2)와 (3, 4) 모두에 대해 0이 네 개 존재한다.

이 이상으로 0이 앞 두 집합에 존재할 수는 없다. 또한, 앞 두 집합에 대해 0이 두 개보다 적게 존재하려면 뒤의 $n-2$개 집합에서 $(0, 0)$을 찾기 때문에 이미 처리된다. 따라서 남는 3개의 쿼리에 대하여 (1, 2), (1, 3), (2, 3)을 확인한 뒤 그들 중 (0, 0)이 존재한다면 출력하고, 모두 '아니다'라는 답을 주었다면 0은 4에 항상 존재하므로 답으로 4를 출력하면 된다.

bool ask(int i, int j) {
    cout << "? " << i << ' ' << j << endl;
    cin >> ans;
    if (ans == 1) {
        cout << "! " << i << endl;
        return true;
    }
    return false;
}

그래서 물어보는 쿼리를 처리하는 ask 함수를 정의해두었다.

    n *= 2;
    while (n > 4) {
        if (ask(n - 1, n)) return;
        n -= 2;
    }
    if (!ask(1, 2) && !ask(1, 3) && !ask(2, 3))
        cout << "! 4" << endl;

그리고, $n>4$에 대하여 $n$을 위에서부터 줄여나가며 내려오는 방식으로 체크하고, 마지막 3개의 쿼리를 확인하는 if문을 달아두었다. ~~왜 풀 때는 생각하지 못하고 이제서야~~

결과

D번도 물론 시도는 했었지만 설명할 수 있는 수준도 되지 못하는 코드인 것 같고, 애초에 업솔브도 못해서...

결과는 A번과 B번을 풀고 6968위로 마무리. C번 하나만 더 맞췄어도 좀 달라졌을 것 같은데... 참 아쉽다. 시간대만 좀 앞이어도 덜 피곤할 때 하지 않았을까 하는 핑계를 대고 싶긴... 하다. 사실 그래도 C번은 못풀지 않았을까ㅎ.

나중에 Div.3 대회가 있다면 그때는 좀 더 많은 문제를 풀어보는 걸로... 그리고, Div.2 대회도 이것저것 더 나가보는 걸로!

이번 Div.2 대회로 레이팅 값이 297 늘었다.

[백준] 서브태스크는 부분점수입니다: 2026 KSA Automata Winter Contest

Sun, 22 Feb 2026 05:21:16 GMT

들어가며

SUAPC Open Contest에서는 C++로 참여를 했는데, 생각해보면 내가 가장 최근까지 계속 썼던 것은 Python이다. 이전에는 JAVA가 가장 익숙하긴 했는데, 사실상 코딩 테스트에서는 JAVA를 잘 쓰지 않는다. 코드 길이가 지나치게 길기 때문에 같은 코드를 입력하더라도 그 시간이 너무나도 길다. 아무튼 그런 의미에서 보면 C++이나 Python은 각각 수행 시간과 코딩 길이에 있어서는 굉장히 이점이 있는 언어들이다. 한편 SUAPC 이후에 다른 대회가 뭐가 있나 보다가 이 대회가 눈에 띄었고, 생각보다 긴 시간동안 대회를 풀어볼 수 있길래 가족끼리 외출한 뒤에 풀어보게 되었다.

설명된 순서는 내가 직접 풀이한 순서대로 적혀 있고, 문제 티어는 2월 22일 오후 2시 16분을 기준으로 하여 갱신되어 있다.

A. 소수가 아닌 수 4 [S4]

Silver 4 #35295 문제 링크 말을 아주 잘 생각해본다면, 이건 생각보다 쉽게 접근할 수 있는 문제다. 정말 몇 분 안 걸려서 생각해낼 수 있었다. (물론 그러고 한 번 틀렸다) / 147

문제의 곳곳에서 생각할 요소들이 존재했다.

적어도 2개의 정수들을 중복 없이 고른다는 것은 2개 이상이기만 하면 모두 답이 될 수 있다는 것이다.
$A_1, A_2, \cdots, A_N$이 '서로 다른 $N$개의 정수'라는 점에서 이들을 고르는 방식은 사실상 1부터 $N$까지의 정수를 $_n C_r$로 구하는 것과 결코 다르지 않다.
합성수인 최소공배수는 어떻게든 여러 숫자를 골라 곱하면 만들어진다.

정수의 개수 $N$의 범위가 2 이상이다. 그러면 두 가지로 나눠서 생각해볼 수 있을 것이다:

$N \ge 3$의 경우
- 가장 작은 $N = 3$이라고만 생각해도, 자연수 $A_1, A_2, A_3$에 대하여 셋 중 하나가 1이라고 해도 나머지 $A_2, A_3$의 최소공배수는 무조건 합성수가 될 수밖에 없다. 이는 문제 조건의 $i \not= j$면 $A_i \not= A_j$라는 조건을 기반으로 생각할 수 있다.
- 즉, 자연수가 3개 이상이라면 랜덤하게 세 개를 골라잡으면 최소공배수는 소수가 아님을 간단하게 알 수 있다.
  - 1, 2, 3처럼 1을 포함하고 두 수가 약수인 경우도,
  - 1, 2, 4처럼 어떤 수의 약수가 포함된 경우도,
  - 2, 3, 4처럼 1이 없어도 모두 그렇다.
$N = 2$의 경우
- 사실상 여기도 서로 다른 두 수가 주어지는 것이기 때문에 $A_1, A_2$가 어떤 한 쪽이 다른 한 쪽의 약수더라도 최소공배수는 그 수가 되므로 크게 문제는 없고, 서로소인 경우는 곱하면 최소공배수가 소수가 되지 않는다.
- 여기에서 생각해볼 것은 1이 포함된 경우이다.
  - 두 수가 $1, p$ ($p$는 소수)로 주어진다면 최소공배수는 $p$이기 때문에 소수가 된다.
  - 두 수가 1, $np$ ($n\ge 2$, $p$는 소수)로 주어진다면 최소공배수는 $np$고 이는 합성수이다.
- 따라서, $N = 2$일 때 확인할 것은 다음과 같다.
  - 어느 것도 1이 아니라면 그 둘을 고르는 게 정답이 된다.
  - 둘 중 하나가 1이라면, 다른 하나가 소수면 답이 존재하지 않는다. 다른 하나가 합성수면 그 둘을 고르는 게 정답이 된다.

첫 번째로 답을 제출할 때는 조금 생각이 짧았었다.

for item in input().split():
    temp = int(item)
    if temp != 1:
        lst.append(str(temp))
        cnt += 1
    if cnt == 2:
        break
if cnt < 2:
    print('NO')
else:
    print('YES')
    print(len(lst))
    print(' '.join(lst))

1이 아닌 수들의 개수를 구해서 그것이 2개 이상이면 그 두 개의 수를 답으로 제출했는데, 이건 $N=2$일 때 ${1, 4}$처럼 주어지는 것을 간과한 답이었다는 것을 뒤늦게 알았다.

B. 아침 점호 [S3]

Silver 3 #35296 문제 링크 케이스 분리를 잘 해서 그리디하게 접근하면 되는 문제이다. 점호를 대신 참여할 수 있는 조건이 '번호 차가 1'만 있는 것이 아니라 '한 변이 인접' 해야한다는 조건이 중요하다. / 171

조건에서 주어지는 번호차 1 + 한변인접 조건을 만족하는 경우가 두 가지 케이스가 존재할 수 있고, 실제로 나는 이 두 케이스로 분리해서 문제를 풀어나갔다.

$N \ge 2$인 경우에 한 개의 세로줄에 대하여 위-아래로 이어진 두 칸은 번호차가 1이며 한 변이 인접하기 때문에 한 사람이 두 개를 처리할 수 있다.
$N = 1$인 경우에 하나의 가로줄로 쭉 이어지는데, 이 경우도 두 칸이 이어지게 되어있다면 번호차가 1이고 한 변이 인접하다.

각각의 열(세로줄) 기준으로 처리하는데, 현재 칸과 다음 칸의 번호를 계산하여 다음 칸도 X이면서 상하로 인접하고 번호 차이가 1인지 확인하면서 맞으면 출력하고 두 칸 처리 후 스킵한다.

이때, 어떤 세로줄의 맨 마지막 칸의 다음 칸은 오른쪽 세로줄의 맨 윗칸이라 서로 인접하지 않기 때문에 $i + 1 < n$의 조건을 두어 이를 제외할 수 있다. 이런 방식으로 서로 인접한 칸에 위치하지 않은 동떨어진 X칸은 그냥 단독으로 해결해주면 된다.

if n > 1:
    # 각 열 기준 처리
    for j in range(m):
        i = 0
        while i < n:
            if grid[i][j] == 'X':
                # 현재 칸의 번호 계산
                current_num = (i + 1) + n * j

                # 다음 칸도 'X'인지 확인 (상하 인접 & 번호 차이 1 만족)
                if i + 1 < n and grid[i + 1][j] == 'X':
                    next_num = (i + 2) + n * j
                    results.append(f"2 {current_num} {next_num}")
                    i += 2  # 두 칸을 처리, skip
                else:
                    results.append(f"1 {current_num}")
                    i += 1
            else:
                i += 1

그렇지 않은 $N=1$의 경우도 비슷한 원리로 풀면 된다!

C. KSA 문자열 3 (부분 성공) [G2]

Gold 2 #35297 문제 링크 서브태스크 하나라도 맞춰보겠다고 일단 부분적으로 규칙을 찾아낸 덕분에 20점의 서브태스크는 성공했지만, 추가 제약 조건 없음 구간에서는 보기좋게 틀려버렸다. / 220 (최종제출)

이번 대회 문제에서 가장 문제풀이에 공을 들였는데 문제 풀이에 성공한 문제이다. 너무 억울하다... 따흐흑...

문제를 정리해보면 이렇다.

좋은 문자열은 KSAKSAKSAK...로 반복되는 문자열이고 그 길이에 맞춰서 자른 형태이다.
문자열에는 두 개의 시행 중 하나를 매회 할 수 있다.
- 인접한 두 개의 문자를 골라 제거
- 맨 앞에 동일한 문자를 2개 추가
이 시행을 최소한으로 하여 좋은 문자열로 바꿀 수 있는 횟수를 구한다.

일단 그래서 무작정 몇 가지 예제를 만들어서 직접 써 보면서 가능한 경우의 수를 체크해보았다. 그래서 일단 같은 문자가 반복되는 형태에 대해서는 일정한 규칙성을 발견하는 데 성공했다.

KKK라는 문자열은 KSA가 되는 것이 목표이다.
- 그럼 앞에 일단 목표 KSA를 2개씩 적어둔다. KKSSAAKSA가 된다.
- 그리고 중간을 지워나간다. KKSSAAKSA~~의 형태로 성립한다.
AAA라는 문자열은 KSA가 되는 것이 목표이다.
- 맨 마지막에 A를 위치하게 하는 것은 AAA에 포함되어 있다. 그러므로 KS만 2개씩 적어둔다. KKSSAAA가 된다.
- 중간을 지워나간다. KKSSAAA의 형태로 성립한다.

이걸 길이를 늘려나가며 발견한다면, 결국 이런 규칙을 볼 수 있다.

어떤 문자열이 같은 문자만으로 이뤄져있다면
- 문자열 길이 $N$에 대한 3으로 나눈 나머지 $R$이
  - 문제 규칙에 따라 $R$이 1, 2, 0일때 각각 K, S, A라 생각해서 이 문자들로만 이뤄져 있는 문자열이라면 : $2(N-1)$회
  - 그렇지 않은 다른 문자로 이뤄진 문자열이라면 $2N$회

if len(set(word)) == 1:
    if word[0] == pat[(word_len - 1) % 3]:
        print(2 * (word_len - 1))
    else:
        print(2 * word_len)

과 같은 형태로 20점을 획득했는데, 나머지 부분을 형성하는 것에 문제가 있었다. 일단 내 아이디어는 이러했다.

최종 만들어야 하는 목표 문자열과 입력으로 주어진 문자열을 뒤에서부터 두 개씩 연달아 체크하면서 부분 문자열을 만든다.
이때, 그 부분 문자열을 선택하는 데 성공했다면 그 앞의 두 개를 체크한다.
그런 방식으로 문자열을 만들었다면 남은 만들어야 하는 부분은 두 번씩 앞에 추가하고 중간을 없애면 만들 수 있다.

예시를 들어보면,

ASKAAAK를 KSAKSAK로 만들려고 해보자. ASKAA[AK] = KSAKS[AK] 이고 나머지는 만들 수 없다.
그러면 앞에 [KKSSAAKKSS]ASKAA[AK]로 붙인다.
나머지는 지우면 된다.
- K[KS]SA[AK]KS[SA][SK][AA]AK

즉, 최소 횟수는 10이 되고, 이는 뒤에서부터 체크해 만든 부분 문자열의 길이를 $m$이라 하고 목표 문자열의 길이를 $M$이라 할 때, $2(M-m)$으로 나타낼 수 있다는 것이 내 풀이의 원래 의도였다. 그런데 어느 부분에서 잘못된 것인지와 반례가 존재하는지 아직도 사실 잘 모르겠다...

D. 책 정렬하기 (부분 성공) [P5]

Platinum 5 #35298 문제 링크 방법이 존재하는지 아닌지에 대한 생각은 어떻게든 했는데, 배치를 하는 방법에 문제가 있었던 것 같다. / 270

책 높이는 순열로 길이 $N$을 이루고, 한 번의 시행은 연속한 책 2권을 골라서 순서를 유지한 채 맨 앞으로 이동하는 것이다. 이때 이것을 $N^2$의 시행 이하로 정렬을 완료하는 순서를 찾는 것이다.

단, 문제에서 포인트는 $0 \le k \le N^2$이기만 한다면 $k$의 최소화 필요성은 없고, 여러 정답이 있다면 아무거나 출력해도 된다.

일단 기본적으로 해본 생각은 이렇다. 예제 입력 1을 기준으로 보자. 어떤 책이 [12453]으로 정렬되어 있을 때, 오름차순 규칙이 깨진 순서쌍은 (4, 3)과 (5, 3)이 있다. 이때, 여기에서 만약 내가 [53] 부분을 앞으로 끌어온다 생각해보자. 그러면 [53124]가 되는데, 여기서 오름차순 규칙이 깨진 순서쌍을 다시 체크해보면 (5,3)(5,1)(5,2)(5,4)(3,1)(3,2)가 된다. 거기에서 [12]를 다시 앞으로 꺼내보자. 그러면 [12534]가 되고, 여기에서 오름차순 규칙이 깨진 순서쌍은 (5,3)(5,4)가 된다. 발견할 수 있는 게 있는가?

어떤 랜덤한 두 개의 책을 맨 앞으로 옮기면 오름차순 규칙이 깨진 순서쌍에 변동이 있는 것은 항상 $2k$개이다. 즉, 처음에 홀수개의 규칙이 깨져 있다면 아무리 옮겨도 홀수가 유지되고, 짝수개의 규칙이 깨져 있다면 아무리 옮겨도 짝수가 유지된다. 완전 오름차순 형태는 깨진 순서쌍이 0개기 때문에 짝수에서나 시행될 수 있는 것이다. 따라서, 오름차순 규칙이 깨진 순서쌍의 개수가 2n개인 경우만이 정렬 가능하다는 것을 분류할 수 있게 된다.

여기에서 내가 선택한 책의 정렬 방법은 이렇다.

가장 먼저, 가장 큰 번호의 책을 옮긴다. [12453]에서는 5를 옮겨야 하는데, 위치할 자리는 맨 오른쪽 끝이다. 한 칸 차이가 나기 때문에 자기 자신을 맨 왼쪽으로 옮기면 [53124]가 되고, 4칸 차이가 나게 되므로 오른쪽이 2n으로 떨어지므로 맨 오른쪽부터 왼쪽으로 옮긴다. [24531] -> [31245]가 된다.
여기에서 다음 큰 번호를 체크한다. 4가 된다. 4는 자리에 위치해 있으므로 무시해도 된다.
다음 큰 번호인 3은 맨 왼쪽에 있고 위치해야 하는 자리는 세 번째이므로 차이는 2이다. 자신의 오른쪽 두 수를 옮긴다. [12345]로 오름차순이 완료된다.

즉, 가장 큰 번호의 책부터 먼저 정렬하되, 그 책이 자신이 위치할 위치에 대해 위치 차이가 짝수라면 오른쪽을 적절히 비워서 위치하게 하고 그렇지 않다면 자기 자신을 적절히 옮겨서 (자신의 왼쪽과 함께 옮기거나, 오른쪽과 함께 옮겨서) 오른쪽을 비우는 방식으로 해결하는 것이다.

서브태스크 1번만 정답이 되었기 때문에 사실상의 좋은 알고리즘을 형성하지 못한 것 같다. 부분 코드는 첨부하지 않겠다.

E. 감정 압축 [G1]

Gold 1 #35299 문제 링크 길이가 $N \le 75$인 부분에서 경우를 나눠서 DP로 처리하는 것이 가능하다고 판단했다. 테이블을 구성하는 부분에서 우여곡절이 조금 있었지만, 다차원 DP 테이블을 차근차근 구성해나가며 문제를 풀이할 수 있었다. / 319

:) 모양 혹은 :( 모양이 $N$개 이어지면 :)N의 표기 형태로 압축이 가능한데, 감정을 $K$개 이하로 반대로 뒤집어 길이를 최소화하되 뒤집더라도 그 모양의 개수가 변하지 않게 하는 것이 중점인 문제이다.

몇 가지 케이스를 적어보면서 이건 DP로 풀만한 문제라고 생각했다. 사실상 좀 저지르듯이 풀었는데, 그래도 일단 해보기로 결정하게 된다. DP 테이블은 dp[현재일][사용한 happy 수][반전수][마지막 감정] 형태로 만들었다.

dp = [[[[INF] * 2 for _ in range(K + 1)] for _ in range(target_happy + 1)] for _ in range(N + 1)]
for length in range(1, N + 1):
    for e in [0, 1]:
        happy_cnt = length if e == 0 else 0
        if happy_cnt > target_happy: continue

        # 현재 구간을 정해진 감정 e로 채울 때 필요한 뒤집기 비용
        flip_cost = sum(1 for i in range(length) if emotions[i] != e)

        if flip_cost <= K: # 뒤집는 최대 한도 K보다 작어야 함
            dp[length][happy_cnt][flip_cost][e] = get_compressed_len(length)

입력을 받아서 일단 :)는 0으로 :(는 1로 대체해두었다. 그리고 숫자를 중심으로 처리할 수 있게 하는데, 일단 앞에서부터 몇 개의 감정 덩어리를 선택해서 구간을 만든다. 그 구간을 정해진 특정 감정 e로 채우려고 할 때 필요한 뒤집기 비용을 sum()을 활용하여 구한다. 그렇게 구한 비용은 최대 한도, 즉 문제에서 주어진 $K$보다는 작아야 한다. 그러면 그 길이를 계산해서 채워둔다.

저기에서 주어진 get_compressed_len()함수는 별 거 없다. 그냥 감정을 축약했을 때의 길이를 반환해주는 것이다.

    def get_compressed_len(length):
        if length == 0: return 0
        if length == 1: return 2  # :)
        if length < 10: return 3  # :)2 ~ :)9
        return 4  # :)10 ~ :)75

그렇게 해서 각각의 칸에 대하여 DP 테이블을 전이시키는데, i, j, k, e의 루프를 돌린다. 각각의 칸이 의미하는 것은

i일차까지 치워서 그중 j일이 :) 모양이고 뒤집기는 k번 사용했으며 그 부분까지의 방금 마지막 끝은 e 모양이다.

라는 뜻이 된다. 그 칸이 INF라면 불필요하고, 그렇지 않다면 그 다음 붙을 건 무조건 반대되는 이모지(1-e)이다. 같았다면 어차피 축약되기 때문이다. 그러면 새로운 감정 덩어리의 길이를 1부터 남은 일수(N-i+1)에 대하여 전부 시도해가면서 새로운 :)의 개수가 K를 넘지 않게 하며 새로운 구간에 대하여 뒤집는 비용을 계산한 뒤, 전체 뒤집은 횟수가 K 이내이면서 그것이 성공하는 케이스라면 DP 테이블의 칸을 갱신해주는 것이다.

필자가 설명을 능숙하게 하는 재주가 부족해서인지 뭔가 내가 적어놓고서도 뭔가 횡설수설한 것 같은데, 요점은 각각의 이모지 모양들을 큰 구간 덩어리로 나눠서 채운 뒤 입력과 비교했을 때 뒤집는 비용이 K보다 적다면 성공하는 케이스로 보면서 칸을 갱신해나가며 DP 테이블을 전이한다는 것이다.

이렇게 해서 E번은 모든 태스크 처리에 성공하게 된다.

결과

5문제를 시도하여 3문제 성공, 2문제 부분 성공하여 48등으로 종료했다. 시간을 더 아끼거나 코드를 줄이거나 할 수 있을만한 실력까지는 아니었던 것 같다. 큰 아쉬움이 느껴지거나 하는 것도 없는 것 같다. 그냥 솔직히 말하면, 문제들에서 조금 큰 벽을 느낀 기분이었다.

이 글을 적는 지금 시점에서 문제들의 업로드가 완료되어 일부 Solved.ac의 랭크가 지정되었는데, 당장 딱 내가 시도해볼만한 난이도들만 시도한 것 같다. (랭크는 이후에도 풀이 기여하시는 분들에 의하여 바뀌는 것으로 알고 있다)

실제로도 대회가 아닌 문제들도 내가 최대한 풀 수 있었던 게 P5~~P4 정도의 난이도였고, G2~~G1 정도가 되면 헷갈려하며 틀리는 것이 일상이었다. 그렇기 때문에 사실상 이 정도를 푼 것만으로도 개인적으로는 크게 만족하는 것 같고, 어떤 의미로는 이렇게 어려운 문제를 내시는 분들은 얼마나 잘 하는 분들일까 하는 큰 벽을 느낀 것 같기도 하다.

앞으로 계속 문제들을 풀면서 감을 잡는 것이 좋을 것 같다는 생각이 든다. 코포나 백준 대회, 그리고 여러 문제들을 풀면서 내 스스로가 문제를 파악하고 적절한 코드를 짜는 연습을 하지 않으면 안 된다는 것을 알기 때문에 내 자신이 성장하기 위한 발돋움의 과정으로 보고 더 열심히 해나갈 생각이다.

[백준] 아무 생각 없이 풀면 시간에 쫓긴다: SUAPC 2026 Winter Open Contest

Fri, 20 Feb 2026 13:12:30 GMT

들어가며

이제 대학교 3학년이 되어가는데, C++이나 Python, Java 등 여러 가지 언어들로 백준을 풀어봤지만 정작 소학회에서 C++을 해놓고 거의 대회는 Java나 Python으로 풀어본 것 같았다. 그래서 내가 어느 정도 할 수 있을까 하는 생각에 문제를 좀 풀어보고 싶었던 터. 그때, 오늘 오전에 딱 발견한 2026 신촌지역 대학교 프로그래밍 동아리 연합 겨울 대회 (SUAPC 2026 Winter) Open Contest를 보았고, 플5인 지금으로서는 그래도 항상 A, B번 정도만 풀던 이전과는 달리 좀 더 풀어낼 수 있지 않을까 하는 생각에 무작정 점심을 먹으러 나갔다 집에 들어오자마자 (열린 시간보다는 조금 늦었지만) 풀어보기에 이른다.

설명된 순서는 내가 직접 풀이한 순서대로 적혀 있다.

A. 유림이와 하람이의 두쫀쿠 대작전 [B4]

Bronze 4
#35277 문제 링크
처음 푼 문제답다. 간단한 수학 구현 문제. / 72

간단한 문제이다. 두쫀쿠를 만드는 데 드는 비용을 모두 더해서 나눠주는 간단한 계산 문제. Python이라면 //로 몫만 챙겨주면 되고, 그게 아니더라도 대부분 int형으로 나눠서 몫만 챙기면 된다. 그냥 머리로 암산해서 나눠줘도 되지만 그런 시간까지 쓰기 싫어서

int doojjonku = 900 + 60 + 600 + 170 + 160 + 110;
cout << n / doojjonku;

int형 변수 두쫀쿠를 만들어주었다(...)
여담이지만 나는 두쫀쿠가 왜 유행했는지 잘 이해하지 못하는 사람 중 한 사람이라. 맛있는지까지 모르겠다...

J. 지하철! 지하철! 몇호선? 몇호선? [G5]

Gold 5
#35286 문제 링크
게임 이론 문제. '일반화'해서 규칙성이나 조건을 찾아내는 것이 늘 어려운 것 같다. 사실 확실하게 답을 찾아냈다기보다는 좀 찍은 감도 없잖아 있는 느낌이다(...) / 111

대회 문제 셋들을 풀어보면 항상 이런 류의 게임 이론 문제가 있다. 나는 그런 문제를 매우 좋아하지 않는다. 도대체 어떤 방식으로 풀어나가야 하는지 감을 잘 못 잡아서 그런 것도 있다. 꼭 이런 류 문제를 풀다 보면 시간을 매우 허망하게 날려버린다...

내가 생각한 방식은 이렇다.

이미 간 곳은 못 간다는 것과, 인접한(-2, -1, 1, 2) 곳만 갈 수 있다는 것이 가장 중요한 규칙이다.
그러면 전체 역을 묶어 보는 것이 중요할 것 같았다.

만약 $N$이 짝수일 경우를 생각해보자. ($N = 2k$, $k$는 자연수)

이 경우 모든 역을 두 개씩 이웃하게 묶을 수 있다. $$(1, 2), (3, 4), (5, 6), \cdots, (N-1, N)$$
호현이 어떤 역을 말하게 되든, 그 역은 이 묶음 중 하나에 해당할 수 있다. 3을 부르면 (3, 4)의 묶음, 8을 부르면 (7, 8)의 묶음 같은 방식으로.
그러면 수아는 항상 그 묶음의 나머지 짝을 부르면 된다.
- 호현이 (a, b)의 (a) 위치를 불렀다면 수아는 (b)를 부른다. 이러면 호현은 (b-2) 또는 (a+1) (a+2) 중 하나를 부를 수 있게 된다.
- 호현이 (a, b)의 (b) 위치를 불렀다면 수아는 (a)를 부른다. 이러면 호현은 (a-2) (a-1) 또는 (a+2) 중 하나를 부를 수 있게 된다.
위 두 가지 경우 모두 또 다른 역의 쌍으로 넘어가는 것이므로 계속 같은 방식을 적용할 수 있다.

그럼, $N$이 홀수일 경우를 생각해보자. ($N = 2k-1$, $k$는 자연수)

이 경우 아무리 잘 묶어도 위의 경우와 달리 한 개의 역이 남는다.
그럼 선공인 호현이는 남는 역을 하나 선점하는 것으로 최선의 수를 잡을 수 있다.
나머지 역들은 다시 짝수 개가 되고, 호현이는 $N$이 짝수일 때의 사실상 '후공' 입장이 되어 짝수에서 수아가 했던 것처럼 짝이 되는 수를 찾아 부르는 전략을 취하면 된다.

맞는 해석인지는 모르겠지만. 코드는 간단하다.

C. 숫자 놀이 3 [G3]

Gold 3
#35279 문제 링크
수학 문제. 진법과 관련된 문제인데, 문제의 설명에 지레 겁먹은 것 치고는 '진법'이라는 개념을 잘 이용한다면 쉽게 접근할 수 있는 문제였어서 금방 풀었다. 포인트는, $n$진법의 한 자리는 $1 \le x < n$의 범위라는 것. / 135

수의 범위가 매우 크다. 진수 범위인 정수 $B$의 범위가 $10^6$인 것부터 심상치 않았다. 어떤 양의 정수 $x$를 $B$진법으로 나타낸 길이가 $l$일 때 $x | l$이라면 $x \div l$의 값을 $x$로 하고 이걸 계속 나눈 결과가 $B$진법에서 한 자리 수라면 날씬한 수라고 부르자는 것이다.

사실 말로만 계속 보면 헷갈려서 직접 해보기로 했다. 예제 입력 1을 기준으로 생각해보면...

10진수의 한 자리로 나타나는 수는 1부터 9이다.
10은 두 자리인데, 이는 $l=2$인 것이므로 $x=10$에 대하여 새로운 $x = 10 \div 2 = 5$이다. 이러면 한 자리 수가 되므로 10은 날씬한 수이다.
11은 소수이다. 두 자리이지만 $l=2$가 약수가 되지 않는다. 따라서 한 자리가 되지 않아 날씬한 수가 아니다.
12는 두 자리이고 2를 약수로 가지므로 $x=6$이 되어 날씬한 수이다.

이걸 이렇게 숫자를 기준으로 올라갈 수도 있겠지만, $n$진법이라는 것이 무엇인지에 의해 나타나는 수들. 그러니까, 문제에서 주어진 이미 $b$진법으로 한 자리인 수들을 기준으로 볼 수도 있겠다.

그러니까, 자명하게 알려진 날씬한 수를 부모로 하여 새로운 날씬한 수를 만드는 것이다.

10진수에서 5는 날씬한 수이다.
- 그러므로 길이가 $l=2$인 것에서 만약 5라는 날씬한 수가 만들어졌다면 그 $x$의 값은 10이다.
- 이때 10은 $b=10$에서 $b^{l-1}=b^1=10$ 이상이므로 두 자리가 되고, $b^l = b^2=100 > 10$이므로 날씬한 수이다.
20진수에서 11은 날씬한 수이다.
- 그러므로 길이가 $l = 2$인 것에서 만약 11이 나왔다면 $x = 22$이다.
- 이때 $b = 20$에서 $b^{l-1}=b^1=20 \le 22$이므로 20진수에서 두 자리 이상임이 보장되고, $b^l = b^2 = 400 > 22$이므로 22는 날씬한 수이다.
- $l = 3$이라면 $x = 33$인데, $b^2 = 400 \le 33$은 말이 되지 않으므로 이는 날씬한 수가 아니다.
120진수에서 90은 날씬한 수이다.
- 그러므로 길이가 $l=2$라면 $x = 180$이다.
- 이때 $b = 120$이므로 $b^1=120 \le 180$이고, $b^2=14400 > 180$이므로 180은 날씬한 수이다.

이런 방식으로 기존의 날씬한 수를 하나씩 뽑아가면서 그것을 부모로 하여 새로운 날씬한 수를 만들어 가려면 기본 정렬이 필요하다는 것을 이해할 수 있고, 이에 따라 우선순위 큐(Priority Queue)를 만들어서 풀이하였다.

오버플로우 방지가 조금 중요했다. $n$진수에 대하여 각 자리 범위를 알기 위해서는 위에서처럼 $n^m$의 계산이 필요하기 때문에, 그것의 전처리 과정에서 범위를 넘진 않나 체크해야 했다. 그래서,

#define ll long long
const ll MAX_LIMIT = 10000000000000000LL;

...

powers.push_back(1);
while (true) {
    ll last = powers.back();
    if (last > MAX_LIMIT / b + 1) {
        powers.push_back(MAX_LIMIT + 7);
        if (powers.size() > 64) break;
    } else powers.push_back(last * b);
    if (powers.back() > MAX_LIMIT && powers.size() > 64) break;
}

다음과 같은 방식을 활용했다. 이는 새로운 날씬한 수를 만들 때도 사용했다. 사실 어려울 건 없다. 가장 마지막으로 구한 $n^p$라는 값이 있을 때, $n^{p+1} = n^p \times n$이고 이것이 오버플로우가 나면 안 되기 때문에 $M_l$(MAX_LIMIT 값) 에 대하여 $\text{last} * b > M_l$인지 확인하기 위해 이를 이항하여 $\text{last} > \frac{M_l}{b + 1}$로 확인하는 것이다.

그리고 전처리에서 64를 둔 것은 $10^{18} < {(2^4)}^{18} = 2^{64}$이기 때문에 그 이상 구하면 오버플로우이기도 하고 범위를 당연히 넘어갈 것으로 보는 것이다. 그게 아니더라도 오버플로우가 발생한다면 push_back으로 MAX_LIMIT+7을 넣기 때문에 if문에 의해서 break로 빠져나가게 된다.

좀 더 쉽게 풀 수 있을 것 같긴 한데 내 생각에서는 이게 최선이었던 것 같다. 그래서 이 전처리 이후 pq를 만들어서 자명하게 알 수 있는 기본 날씬한 수들을 집어넣고 이걸 기반으로 빼 나가며 출력 - 새로운 수 생성을 거치게 했다.

ll tar = x * l;
if (tar >= powers[l-1] && (l >= powers.size()-1 || tar < powers[l]))
    pq.push(tar);

검증은 위와 같이 거치게 했다. 위에서 120진수로 날씬한 수 90을 기반으로 하여 새로운 180이라는 날씬한 수를 확인하는 과정을 그대로 쓴 것이다.

M. 괄호 문자열 카드 [S2]

Silver 2
#35289 문제 링크
어디서 본 듯한 올바른 괄호 문자열 만들기 문제 형태. 근데 )( 모양의 처리를 굉장히 이상하게 하기 시작하면서 하드코딩으로 시간을 대놓고 너무 많이 잡아먹었다. 포인트는, 앞과 뒤만 대충 묶어둔다면 )( )( )(처럼 연달아서 모두 털어낼 수 있다는 것. / 206

내가 이걸 왜 이상하게 풀었는지 정말 후회된다. 그렇다면 한 문제 정도는 더 풀었을텐데...

처음 보면서 생각한 건 개수가 생각보다 많이 들어올 수 있기 때문에 일반적으로 이런 괄호 문자열에서 많이 접한 자료구조형 문제는 아니라 생각했다. 그래서, 우선순위를 나눠서 처리하자는 생각에 이른다. 하지만 그 분류가 굉장히 잘못됐었다.

분류 E는 () 모양이다. 맨 처음에 모두 털어내도 된다. 그 자체로 문자열이 된다.
분류 F는 까다롭지만 문자열 길이가 2인 우선순위가 있는 것이므로 이것을 처리한다.
- 여기에서 이것을 처리하려면 앞뒤의 모양이 서로 같아야 한다. 그러므로, BFD -> BFCC -> AAFD -> AFC 순서로 처리한다 (...)
그 다음으로 큰 쌍은 B-D를 짝짓는 쌍이다.
- 그 이후로는 B보다 개수가 적은 A를 처리하고, D보다 적은 C를 처리한 다음, 마지막으로 남는 A-C를 처리한다.

여기에서 문제가 된 것은 중간의 F 부분. 저걸...

    // F는 까다로우면서도 길이가 길기 때문에 먼저 처리
    // 우선순위는 BFD -> BFCC -> AAFD -> AFC 순서임
    if (b * d != 0 && f > 0) { // 둘 다 0이 아니라면
        int cnt = min(min(b, d), f);
        answer += cnt * 6; // 완성되는 한 쌍은 (( )( ))
        b -= cnt;
        d -= cnt;
        f -= cnt;
    }
    if (b * c != 0 && f > 0) {
        int cnt = min(min(b, c / 2), f);
        answer += cnt * 6; // 완성되는 한 쌍은 (( )( ) )
        b -= cnt;
        c -= cnt * 2;
        f -= cnt;
    }
    if (a * d != 0 && f > 0) {
        int cnt = min(min(a / 2, d), f);
        answer += cnt * 6; // 완성되는 한 쌍은 ( ( )( ))
        a -= cnt;
        d -= cnt * 2;
        f -= cnt;
    }
    if (a * c != 0 && f > 0) {
        int cnt = min(min(a, d), f);
        answer += cnt * 4; // 완성되는 한 쌍은 ( )( )
        a -= cnt;
        d -= cnt;
        f -= cnt;
    }

이러고 짜고 있었다. 진짜 뭐하니... 이러면 문제가 되는 건, )(를 꼭 한 개씩만 사용하게 된다. 개수가 무조건 남게 된다. 가령, A 1, C 1, F 120의 극단적 예시에서는 AFC 하나만 처리해서 답을 4로 내는 기행을 저지른다.

이러고서 뭐가 잘못됐나 아주 한참을 고민한 것 같다. 그래서 F는 최소한의 쌍으로 미리 처리해서 모두 털어낸다는 아이디어를 얻고 나서는,

    if (f > 0) {
        if (b > 0 && d > 0) { // (( )( )( ... )( )) 같은 방식
            answer += 2 * f + 4;
            b--; d--;
        }
        else if (a > 0 && c > 0) { // ( )( ... )( ) 같은 방식
            answer += 2 * f + 2;
            a--; c--;
        }
        else if (a >= 2 && d > 0) { // ( ( )( )) 로 처리해야 하면
            answer += 2 * f + 4;
            a -= 2; d--;
        }
        else if (b > 0 && c >= 2) { // (( )( ) ) 로 처리해야 하면
            answer += 2 * f + 4;
            b--; c -= 2;
        }
    }

이런 방식으로 해결하였다. 앞에서 E를 처리하고 뒤에서 남은 A, B, C, D를 처리하는 것은 굳이 설명하지 않아도 될 이야기다. 아쉬운 건, 조건 분기를 너무 많이 잡고 하드코딩을 했나 싶다는 생각이다.

H. 신촌 방수 계획 [P5]

Platinum 5
#35284 문제 링크
저번 학기에 자료구조 수업을 들으면서 맨 마지막에 배운 최소 비용 신장 트리, 그리고 소학회 알고리즘 스터디에서 배웠던 Union-Find를 활용해서 생각보다 금방 풀어냈다. 개인적으로는 내가 이걸 생각해냈다는 것에 굉장히 자랑스러웠던 문제. 포인트는 우산과 지붕 간선을 분류하는 것이었다. / 251

처음에는 가장 마지막의 그림을 그리지 못하고 그 왼쪽까지만 생각했다. 그래서 최소 비용 신장 트리를 이루는 각 간선의 양쪽 끝에서 우산을 두는 비용을 합쳐서 지붕의 비용보다 적으면 대체가 가능한 것이라는 생각을 했었다. 그렇게 어찌어찌 구현한 1트에서는 당연히 답이 되지 않았다. 간과한 게 있었다. 문제에서 주어진 문장.

따라서 이후 어떤 통로를 지나더라도 비를 맞지 않고 이동할 수 있다. 빌린 우산을 다시 반납할 필요는 없다.

이 문장을 생각했어야 했다. 그러니까, 사실상 어떤 곳에서 우산을 빌릴 수 있다면 다른 곳은 그 우산으로 어디든 통로를 통해 갈 수 있다. 보관함 없이 지붕만 연결하는 경우가 반드시 존재하므로 그렇게 MST를 한 번 계산한다.

    sort(roof_edges.begin(), roof_edges.end());
    for (int i = 1; i <= n; ++i) parent[i] = i;

    ll only_roof_cost = 0;
    int roof_cnt = 0;
    for (const auto& e : roof_edges) {
        if (Union(e.u, e.v)) {
            only_roof_cost += e.w;
            roof_cnt++;
        }
    }

그리고 가상의 0번 노드를 두고 그걸 모든 건물과 이은 다음, 전체에서 MST를 만드는 것까지 계산했다.

    sort(all_edges.begin(), all_edges.end());
    for (int i = 0; i <= n; ++i) parent[i] = i;

    ll with_umbrella_cost = 0;
    int total_cnt = 0;
    for (const auto& e : all_edges) {
        if (Union(e.u, e.v)) {
            with_umbrella_cost += e.w;
            total_cnt++;
            if (total_cnt == n) break; // 노드 개수는 n+1이 됨 (0번 추가)
        }
    }

그렇게 두 경우의 비용을 비교해서 최소 비용을 출력하는 것으로 문제를 해결했다. 개인적으로는 늘 트리나 그래프 문제는 내 발목을 잡고 도망치게 만든 문제들이었는데 이런 문제를 내가 내 힘으로 풀어냈다는 것에 가장 큰 성취감을 느꼈다.

E. 가지가지 (오답) [G3]

Gold 3
#35281 문제 링크
마지막으로 붙들고 있던 문제. Ad hoc + 구현 문제인 것 같은데, 손으로 규칙은 어떻게든 만든 것 같은데 이게 맞나 고민하는 시간과 구현하면서 계속 패턴이 안 나온 것이 패착이었던 것 같다.

이 문제도 직접 그리고 해 보면서 규칙을 찾아내려고 애를 썼다. 분명히 규칙이 존재할 것 같았고, 크기도 크기지만 이런 느낌의 문제(체스판 문제와 비슷하게 느꼈다)를 풀어본 적도 있기 때문에 분명 단순히 구현하는 어떤 규칙성이 존재할거라고 생각했다. 하지만 생각보다 그 규칙이라는 것이 좀 딱 떨어지지 않는 기분이 들어서 내가 맞게 찾았나 계속 생각하면서 시간을 써먹은 것 같다.

일단 그래서 내가 생각한 규칙으로 $m \times n$ 크기에 대하여

$m$과 $n$이 모두 짝수이거나 모두 홀수여야만 놓을 수 있다.
- 어느 한 쪽이 짝수인 경우 한 개 이상의 열에 대하여 꼭지가 짝수개로 배치되거나 놓이지 않게 됨을 실험적으로 확인했다.
- 반대로 $n \times n$의 정사각형은 $2 \times 2$ 크기 이하를 제외한 모든 크기에 대하여 배치가 가능했다.
위의 규칙에 대하여 모든 $m \times n$ 크기에 대하여 $k = \text{min}(n, m)$에 대해 $k\times k$를 먼저 배치하고, 나머지는 한 개의 열에 모두 꼭지를 넘겨주는 방식을 택하여 배치한다.
- $m$과 $n$은 모두 홀수 혹은 짝수이기 때문에, 더 작은 것이 $k$가 되므로 가령 두 홀수가 $m < n$이라면 $n - m = 2p - 1 - (2q - 1) = 2(p-q)$ (단, $p, q$는 자연수)가 되고, 이는 짝수가 된다.
- 따라서 한 개의 열이나 행에 이들에서 발생하는 꼭지의 개수를 몰아준다고 해도 $k \times k$에서 배치한 꼭지는 모두 1개이므로, $1 + 2(p-q)$가 되므로 홀수임이 유지된다.

다음과 같이 배열을 해보려고 코드를 짜다가 실패했다. 아마 예상하기로 내가 여러 가지 테스트케이스를 만들어 체크했는데도 제출하고 얼마 안 되어 바로 틀렸습니다가 뜬 걸 보면, 코드 내에서 $n \times m$의 크기가 $2 \times 2$ 이하인 것을 예외처리하지 않은 것에서 걸린 건 아닐까 하는 생각이 들었다. 그리고 무엇보다 문자열화하는 부분이 2차원 배열에 식을 써넣는 하드코딩이었던 것도 한몫한 것 같다.

~~놀랍지도 않지만 이게 아직 코드 일부이다~~

적어도 도미노의 특정 좌표를 받아 가로/세로로 'g'와 'G'를 일괄 처리하는 함수라도 만들 걸 하는 생각이 시간이 다 끝나고 나서야 들었다.

void horiz_domino(int lr, int lc) {
    grid[lr][lc] = 'g';
    grid[lr][lc + 1] = 'G';
}

void verti_domino(int hr, int hc) {
    grid[hr][hc] = 'g';
    grid[hr + 1][hc] = 'G';
}

이거라도 했으면 그래도 좀 더 패턴을 맞추고 검증하는 시간이 줄어들지 않았을까 하는 아쉬움이 있다.

결과

5문제를 풀었고, 23등에 자리했다. 시간을 좀 아껴서 저 가지가지 문제를 풀었으면 좋았을텐데 하는 아쉬움이 있지만, 그래도 이 정도까지 풀 수 있었어서 좋았던 것 같다. 이전의 나라면 아마 A번 정도 풀면 고작이지 않았을까...? ~~근데 Python으로 했으면 좀 더 빨리 할 수 있지 않았을까 하는 생각도 든다 왜 C++을 골랐을까~~

+ 26.02.22

어떻게 딱 풀어낸 것들이 난이도가 낮은 것부터 풀려 있다(...)
어쩔 수 없지 이게 내 실력인걸...? 따흐흑 난 언제쯤 플래도 무난히 도전해볼수 있을까...

한 대학생이 Convex Hull 알고리즘 공부하다가 만든 프로그램

Tue, 23 Dec 2025 12:44:11 GMT

시작은 별 거 아니었다

2학년 2학기를 다니고 있는 대학생인 나는, 이번 학기에 들은 컴퓨터 그래픽스 과목의 OpenGL을 썩히고 싶지 않았다. 마침 종강도 했겠다, 가만히 놀지 말고 뭐라도 해볼까 싶긴 했지만 뭘 해야 할까 고민도 되고 막상 하려니까 아무 생각도 안 들었다. 그래서 백준을 풀고 있었는데, 그때 Convex Hull과 관련된 문제가 보였다. 분명 그래픽스에서도 다뤘던 것 같은데 하고 생각해보니, 마음만 먹으면 이걸 시각화할 수 있는 프로그램 정도는 만들 수 있지 않을까? 하는 생각이 들었다. 해당 문제의 링크 는 여기를 눌러 확인할 수 있다.

대략적인 인터페이스 구상

어쩌다 보니 모바일 모양처럼 되긴 했는데, 저걸 모두 구현하는 건 천천히 진행하더라도 일단 중요한 건,

점을 사용자가 임의대로 화면에 찍을 수 있게 하자.
해당 점들에 대하여 버튼을 클릭하면 Convex Hull 알고리즘으로 구현된 결과를 볼 수 있게 하자.
일괄적으로 지우거나 할 수 있는 버튼도 만들자.
사용자가 지정한 점 개수와 시드 번호를 통하여 랜덤하게 생성할 수 있게 하자.
txt나 csv 등의 파일로 파일 입출력을 지원할 수 있게 하자.

이 정도는 무조건 구현해보자는 생각이 들었다.

그렇게 만들어진 결과

생각보다 마음에 드는 결과가 나왔다. 위쪽의 Import/Export 버튼을 활용하여 .csv 파일로 내보내기도 가능하고, 오른쪽 상단에서 시드 값과 점의 개수 역시 지정할 수 있다. 화면에서는 점을 사용자가 임의대로 찍을 수 있고, 아래의 Get Convex Hull 버튼을 통하여 결과를 확인할 수 있다. Erase All 버튼으로 전부 지울 수도 있다.

위 csv 파일의 값처럼 저장되는데, x축과 y축을 각각 픽셀 개수로 지정하였다. -1부터 1까지의 normalized coordinate를 사용할 수도 있었지만, 사용자의 입력을 받기 위해서는 생각보다 정규화 좌표계를 쓰는 것은 소수점이 길어지거나 근사값으로 입력해야 하기 때문에 원하는 결과를 보기 어려울 거라는 생각이 들어 픽셀을 선택하게 되었다.

만들면서 생각한 것들

#1 OpenGL Shading Language와 OpenGL

OpenGL을 다루면서 사실 HLSL 코드를 그렇게 잘 아는 것도 아니고, 이런저런 자료들을 인터넷에서 찾으려면 낮은 버전을 활용할 수도 있었겠지만 그래픽스 강의를 들으면서 배운 것은 #version 410 core로 시작하는 OpenGL Shading Language였기 때문에 그걸 활용해보기로 결정했다.

#version 410 core
layout (location = 0) in vec2 aPos;
void main() {
    gl_Position = vec4(aPos.x, aPos.y, 0.0, 1.0)
}

데이터를 버퍼와 VAO(Vertex Array Object)를 기반으로 관리해야 하기 때문에 셰이더 코드를 다음과 같이 작성하였고, 파일 입출력 시에는 사용자 친화를 위해 픽셀 좌표를 활용하여 렌더링 직전에 다시 변환하는 방식을 택하였다.

inline void exportPoints(const std::string& filename, const std::vector& points, float width, float height) {
    std::ofstream outFile(filename);
    if (outFile.is_open()) {
        for (const auto& p : points) {
            float px = (p.x + 1.f) * (width / 2.0f);
            float py = (1.f - p.y) * (height / 2.0f);
            outFile << px << ',' << py << "\n";
        }
        outFile.close();
        std::cout << "Points exported to " << filename << std::endl;
    }                                                              
    else {
        std::cerr << "Failed to open file for export: " << filename << std::endl;
    }
}

위 코드는 특히 export 과정을 다루는데, 잘 보면 normalized coordinate로 옮겨지기 전의 상태와 아닌 상태를 구분하기 위하여 계산 과정을 걸치는 것을 볼 수 있다. 이렇게 하게 된다면 픽셀 좌표는 음수나 실수 형태를 만들지 않아도 되기 때문에 사용자가 메모장으로 csv 파일을 직접 열어서 좌표를 수정하는 것도 어렵지 않게 된다.

#2 Convex Hull 알고리즘

이 프로그램의 핵심 로직인데, 여러 알고리즘 중에서 가장 직관적이고 효율적으로 볼 수 있다고 생각하는 Graham Scan 알고리즘을 활용하였다. 가장 중요한 포인트는 세 점에 대한 방향성, 즉 CCW(Counter-ClockWise)를 판별하는 것이다. convexhull.h 파일에 별도로 이 부분들이 관리되어 있다.

inline float counterClockWise(Point a, Point b, Point c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

inline float distSquared(Point p1, Point p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

inline bool compare(Point a, Point b) {
    float order = counterClockWise(pivot, a, b);
    if (order == 0) return distSquared(pivot, a) < distSquared(pivot, b);
    return order > 0;
}

점을 발견하여 기준점을 잡고 각도 순서로 정렬한 뒤, 스택 구조를 활용하여 정확한 상황을 혹인한 뒤 외곽선으로 인정하게 되는 과정인데, 이것을 실질적으로 시각화하기 위한 것이 이번 프로그램을 만들게 된 목적이었기 때문에 일직선상에 놓이는 점의 예외 케이스 처리를 위하여 거리 계산이 추가되는 등 생각보다 시각화에서는 디테일한 예외 처리도 필수적인 요소였다.

#3 인터페이스 제작을 위한 ImGui

기본 시안으로서 프로토타입 인터페이스를 대략 잡고, 그걸 구현하는 과정에서 ImGui라는 것을 알게 되었다. imgui(dear imgui)는 게임 엔진의 개발 등에도 널리 쓰이는 immediate mode gui 라이브러리인데, 어플리케이션의 디버그 인터페이스나 개발 도구 및 실험적인 UI를 빠르게 추가하는 데 사용하며 특히 게임 개발이나 그래픽 프로그래밍 같은 실시간 어플리케이션의 개발에서 많이 사용한다고 한다. Win32 API나 다른 UI 라이브러리보다 훨씬 가볍게 OpenGL에 얹을 수 있기에 사용하기에 훨씬 좋았다고 생각한다.

    IMGUI_CHECKVERSION();
    CreateContext();
    ImGuiIO& io = GetIO();

    io.Fonts->AddFontDefault();
    io.FontGlobalScale = 1.5f;

    ImGui_ImplGlfw_InitForOpenGL(window, true);
    ImGui_ImplOpenGL3_Init("#version 410");

    StyleColorsDark();
    ImGuiStyle& style = GetStyle();

    style.WindowRounding = 5.0f;
    style.FrameRounding = 5.0f;
    style.Colors[ImGuiCol_Button] = ImVec4(0.2f, 0.2f, 0.2f, 1.0f);
    style.Colors[ImGuiCol_ButtonHovered] = ImVec4(0.3f, 0.3f, 0.3f, 1.0f);

메인 파트에서 초기화와 함께 기본 설정을 하는 부분인데, 생각보다 직관적으로 사용할 수 있는 경우가 많았고 그럼에도 확실한 기반을 만들 수 있다는 것이 굉장히 편리한 것 같다.

    Begin("TopBar", nullptr, ImGuiWindowFlags_NoTitleBar | ImGuiWindowFlags_NoResize | ImGuiWindowFlags_NoMove | ImGuiWindowFlags_NoScrollbar);
    Text("Convex Hull Tool with OpenGL 4.1 Core");

    SameLine(600);
    if (Button("Import with .csv", ImVec2(180, 25)))
        importPoints("points.csv", userPoints, hullPoints, screenW, screenH);
    SameLine();
    if (Button("Export with .csv", ImVec2(180, 25)))
        exportPoints("points.csv", userPoints, screenW, screenH);

    SameLine(screenW - 150);
    TextDisabled("%zu Points", userPoints.size());
    End();

특히 Begin()과 End() 안쪽에 상세한 것을 설정하는 방식은 왜인지는 모르겠지만 양쪽의 bracket 안에 파트를 나눠 인터페이스를 제작하는 방식의 HTML 역시 생각나게 하는 것 같았다. 그래서인지 조금 더 직관적으로 어떤 방식으로 코드를 짜면 될 지 생각하기 좋았다.

#4 C++과 모듈화

프로젝트의 구조적인 완성도를 위하여 모듈화를 확실히 했는데, 모든 코드를 main.cpp에 때려박을 수도 있었지만 일단 하면서 내 스스로부터가 뭔가 정리하기도 영 애매해지는 걸 느꼈고, 기능의 추가를 이렇게 번거롭게 한 코드 내에서 #include문 넣고, 아래로 내려가서 함수 만들고, 뭐 하고... 하는 그런 과정은 영 마음에 들지 않았다. 그래서 역할별로 헤더 파일을 분리해 구획화하였다.

myshader.h는 셰이더를 컴파일하고 프로그램을 로드하는 것을 관리하는 헤더 파일이다.
convexhull.h는 순수 수학적 알고리즘 로직을 분리하여 convex hull 알고리즘을 조금 더 직관적으로 구현하기 위하여 만든 헤더 파일이다.
fileio.h는 파일 시스템에 접근하여 데이터를 읽거나 써서 내보내는 변환을 거치는 헤더 파일이다.

이런 방식을 채택한다면 이후에 새로운 기능을 만들거나 추가해보더라도 더 쉽게 디벨롭이 가능할 것 같다.

더 해보려고 하는 것

특정 점을 기준점으로 잡아 그 기준점에서 convex hull을 뻗어나가는 방식을 애니메이션으로 보여주는 것은 어떨까?
일정 범위에 대해서 주어진 (가령, -10에서 10 사이) 좌표들에 대해서 자체적으로 스케일을 조절하여 시각화해주는 건 어떨까?
인터페이스 내에서 선 색 조절, 점 크기 조절 등 조금 더 사용자 친화적인 인터페이스를 만들 수 있지 않을까?
사용자의 마우스 커서가 특정 점에 가까워지면, 그 점에 대한 좌표 정보나 convex hull 포함 여부 등의 정보를 제공하는 작은 창을 띄우는 건 어떨까?

링크

깃허브의 아래 링크에서 프로그램을 직접 확인해볼 수 있다! 👉 Convex Hull 구해주는 프로그램 (깃헙/Github)