인하대학교 프로그래밍 대회(IUPC) 2021

2022 PPC 문제를 출제하고 있어서 다른 문제도 볼 겸으로 처음부터 끝까지 풀어보았다.

문제 링크

A. 스키테일 암호

문제 설명

스키테일 암호는 막대에 문자열이 적힌 종이를 말아 암호를 해독하는 기법이다.

문자열의 길이 \(N\)이 주어지고, 맨 처음 글자부터 \(K\)번째 글자마다 읽을 때, 해독 결과를 출력하는 문제이다.

알고리즘

매 \(K\)번째 글자를 출력하면 된다.

B. 오델로

문제 설명

\(N \times N\) 크기의 오델로 게임 판이 주어진다. \( (N \le 500) \)

현재 나는 흑돌일 때, 어디에 두어야 가장 많은 백돌을 둘 수 있는지 출력해야 한다.

알고리즘

각 칸마다 흑돌을 두었을 때, 뒤집을 수 있는 백돌의 개수를 구하고 최댓값을 출력하면 된다.

뒤집을 수 있는 백돌의 개수는 8방향마다 백돌이 연속으로 있고 그 끝에 흑돌이 있는지 검사하고, 그런 방향의 백돌 개수의 합이 된다.

모든 위치마다 검사를 진행하고, 각 검사의 시간복잡도는 \(O(N)\)이므로 총 시간복잡도는 \(O(N^3)\)이다.

C. 균형 삼진법

문제 설명

평범한 3진법이 밑이 3이고, 자릿수가 0, 1, 2로 이루어졌다면, 균형 3진법은 밑이 3이고, 자릿수가 -1, 0, 1로 이루어져 있다. 10진법으로 이루어진 숫자 \(N\)이 입력으로 들어올 때 이를 균형 3진법으로 나타내야 한다.

알고리즘

먼저 \(N\)이 음수인 경우에는 \(-N\)을 균형 3진법으로 나타내고, -1을 1로, 1을 -1로 바꿔주면 되기 때문에, \(N\)이 양수인 경우만 고려해보자.

\(N\)을 3진법으로 나타냈을 때 \(k\)자리라 가정하자. 이 결과에서 0, 1, 2를 각각 -1, 0, 1로 바꿔보면, 이 결과는 \(N - \sum_{i=0}^{k-1} 3^i \)을 균형 3진법으로 나타낸 결과가 된다.

이를 거꾸로 생각하면, 먼저 \(N\)을 균형 3진법으로 나타냈을 때 \(k\)자리라 가정하면, \(N + \sum_{i=0}^{k-1} 3^i \) 을 3진법으로 변환한 뒤, 0, 1, 2를 -1, 0, 1로 바꾸면 된다.

따라서 모든 자연수 \(k\)에 대해 \(N\)을 균형 3진법으로 나타내고, 그 결과가 \(k\)자리이면 나타낸 결과를 출력하면 된다.

D. Aging

문제 설명

컴퓨터 구조의 프로세스 스케쥴링을 하는 문제이다.

프로세스의 시작 시점, 실행 시간, 우선순위 값이 주어진다. 컴퓨터는 현재 실행해야 할 프로세스 중, 우선순위 값이 큰 프로세스, 실행 시간이 짧은 프로세스, 번호가 먼저 부여된 프로세스 순으로 우선순위를 매겨 프로세스를 실행한다.

이 때, 우선순위가 낮아 특정 프로세스가 계속 실행될 수 있기 때문에 매 단위시간마다 대기중인 프로세스의 우선순위를 1만큼 증가시킨다.

프로세스의 실행 순서를 출력해야 한다.

알고리즘

대기 중인 프로세스의 우선순위 값을 1만큼 증가시키는 대신, 아직 실행이 되지 않은 프로세스의 우선순위 값을 1만큼 감소시킨다는 관점으로 접근하면 쉽게 풀 수 있다.

프로세스의 시작 시점이 \(t\)이고, 우선순위가 \(p\)라 하면, 매 단위시간마다 우선순위를 1만큼 증가하는 대신 우선순위를 \(p-t\)로 생각하여 풀 수 있다.

그 이후에는 우선순위 큐를 이용하여 문제를 풀 수 있다. 위 프로세스의 비교 조건대로 우선순위 큐를 정의하여 시작 시간이 된 프로세스들을 우선순위 큐에 넣어 어떤 프로세스를 실행할 지 관리하면 된다.

E. 두 반으로 나누기

문제 설명

\(N\)명의 친한 친구 쌍 \(M\)개가 주어진다.

이 중에서 최대 \(K\)개의 친구 쌍을 끊어 이 친구들을 두 분반으로 나누려고 한다.

이때, 각 분반에는 친한 친구 쌍이 없어야 한다.

\(K\)개의 친구 쌍을 1번부터 차례대로 끊을 때, 최소 몇 개를 끊어야 두 분반으로 나눌 수 있는지 출력해야 한다.

알고리즘

먼저 이 문제는 정점이 \(N\)개이고 간선이 \(M\)개일 때, \(K\)개의 간선 중 차례대로 최소 몇 개를 끊어야 이분 그래프가 되는지를 구하는 문제이다.

먼저 이분 그래프가 아닌 그래프의 특정 간선을 끊은 후에 이분 그래프가 되는 지 확인하는 것은 어렵다. 하지만 이분 그래프에서 특정 간선을 추가한 후에도 이분 그래프인지 확인하는 것은 가능하다. 따라서 \(K\)개의 간선을 모두 끊은 뒤 하나 씩 연결해가면서 이분 그래프가 

이분 그래프는 모든 정점을 2개의 색깔로, 그리고 간선으로 연결된 두 정점이 색깔은 다르도록 색칠할 수 있다.

따라서 \(K\)개의 간선을 제외한 \(M-K\) 간선만으로 이루어진 그래프를 두 색깔로 칠하면서 이분 그래프인지 확인한다.

그 이후, \(K\)개의 간선에 대해 연결된 두 정점의 색깔이 다른 지 순서대로 확인한다.

이렇게 할 경우 시간복잡도 \(O(N + M)\) 안에 해결할 수 있다.

F. IUPC와 비밀번호

문제 설명

문자열 \(S\)의 비밀번호를 아래 순서로 만든다.

1. \(S\)에서 각 문자의 위치를 뒤섞는다.

2. 문자열의 앞과 뒤에 0개 이상의 아무 문자를 추가한다.

3. 문자열의 한 글자를 선택해 다른 문자로 바꾼다.

문자열 \(S\)가 주어지고, \(N\)개의 문자열 \(T\)가 주어질 때, 각 문자열 \(T\)가 \(S\)의 비밀번호가 될 수 있는지 여부를 출력해야 한다.

알고리즘

먼저 문자열 \(T\)의 길이가 문자열 \(S\)의 길이보다 짧으면 불가능하다. 따라서 문자열 \(T\)가 \(S\)와 길이가 같거나 더 긴 경우만 고려해보자.

슬라이딩 윈도우 기법을 적용하면 문자열 \(T\)에서 길이가 \(|S|\)인 모든 부분 문자열 \(T_i\)의 알파벳의 개수를 \(O(T)\)안에 구할 수 있다.

문자열 \(T_i\)와 문자열 \(S\)의 각 알파벳의 개수를 알 수 있다면, 문자열 \(T\)가 문자열 \(S\)의 비밀번호가 될 수 있는지 계산할 수 있다. 만약 2종류 알파벳을 제외한 모든 알파벳의 개수가 똑같고 2종류의 알파벳 개수는 정확히 하나만큼 차이난다면 \(T\)는 \(S\)의 비밀번호가 될 수 있다. 또한, \(T\)가 \(S\)보다 길고 모든 알파벳의 개수가 똑같아도 \(T\)는 \(S\)의 비밀번호가 될 수 있다.

G. 최단최단경로

문제 설명

가중치가 있는 그래프가 주어졌을 때, 두 정점 \(x\)와 \(y\)의 최단거리를 구하면 된다.

만약 최단 거리가 여러 개라면 최소한의 정점을 거쳐 갈 수 있어야 한다.

최단 거리, 이 때 거쳐야 하는 정점의 최소 개수, 그리고 이러한 경로의 개수를 출력해야 한다.

알고리즘

먼저 원래 간선의 바용이 \(c\)라 하면 단순히 간선의 비용을 \( (c, 1)\)로 바꾸면 정점의 개수를 고려할 수 있다.

이 상태에서 다익스트라를 돌리면 최단 거리와, 정점의 개수는 구할 수 있다.

다익스트라를 이용하면 경로의 개수도 구할 수 있다. 각 정점마다 최단 거리로 가는 경로의 개수를 \(cnt\) 배열 하나로 관리하여 구할 수 있다.

출발 정점인 \(x\)의 경로는 \(cnt[x] = 1\)이다. 그 이후 \( (u, v) \)가 연결된 간선으로 업데이트를 할 때, 최단경로보다 짧아진다면, \(cnt[v] = cnt[u]\)로 업데이트하고, 만약 기존 최단경로와 길이가 똑같다면, \(cnt[v] = cnt[u] + cnt[v]\)로 업데이트하면 된다.

H. 난민

문제 설명

2차원 좌표 상에 총 \(N\)개의 난민 거주지가 있고, \(x\)좌표는 0인 점들 중 한 점에 정수시설을 설치한다.

난민 거주지와 정수시설의 맨해튼 거리의 합이 최소가 되도록하는 지점에 정수시설을 처리하고자 한다.

매 순간 \(N\)개의 난민 거주지에 차례대로 난민이 이주해온다. 난민이 이주한 순간마다 최소 맨해튼 거리의 합을 출력해야 한다.

알고리즘

이 문제는 두 개의 우선순위 큐를 이용하여 중앙값을 찾는 기법을 활용하면 풀 수 있다.

먼저 \(x\)좌표는 고정되어 있기 때문에 \(y\)좌표만 고려하여 계산한 뒤, 마지막에 \(x\)좌표의 절댓값의 합을 더해주는 방식으로 \(x\)좌표를 처리해줄 수 있다.

\(y\)좌표의 경우에는 \(y\)좌표의 중앙값 \(Y\)를 찾는다. 그 후, \(Y\)보다 작은 \(y\)좌표들의 개수 \(cnt\)와 합 \(sum\)을 실시간으로 계산해주면 \(sum - Y \times cnt\)가 \(Y\)보다 작은 \(y\)좌표들을 가진 점들의 맨해튼 거리가 된다. \(Y\)보다 큰 \(y\)좌표들도 똑같은 방식으로 계산해줄 수 있다.

I. 판치기

문제 설명

판치기를 할 때마다 \(N\)개의 동전 중 서로 다른 \(K\)개의 동전을 뒤집을 수 있다.

현재 동전 상태가 주어질 때, 최소 몇 번을 판치기해야 모두 뒷면으로 만들 수 있는지 출력하면 된다.

알고리즘

dp로 풀 수 있다. 뒤집은 동전 개수에 따라 최소 판치기 횟수를 저장하면 풀 수 있다.

\(x\)개 동전이 뒷면인 상태에서 \(y\)개 동전이 뒷면이도록 만들 수 있을 때 점화식은 아래와 같다.

\( dp[y]=\min (dp[x]) + 1\)

점화식 자체는 쉬워보이지만 무조건 \(K\)개를 뒤집어야 하기 때문에 \(y\)개로 만들 수 있는지 여부를 확인할 때 주의해야 한다.

예를 들어, 6개중 4개가 뒷면이고, \(K\)가 4라면 한 번의 판치기로는 모두 뒷면으로 만들 수 없다.

J. 사탕나무

문제 설명

정점이 \(N\)개인 트리가 주어진다. 각 정점에는 사탕이 하나 있다.

특정 정점을 선택하고, 그 정점과 거리가 \(K\) 이하인 모든 정점의 사탕을 얻을 수 있다. \( K \le 20\)

한 정점을 선택하여 얻을 수 있는 사탕의 최대 개수를 출력해야 한다.

알고리즘

\(K\)의 범위가 작다는 사실을 활용하여 전처리를 한 뒤 계산해야 한다.

먼저 트리의 루트를 임의로 1로 잡는다. 그 후, \(dp[n][i]=\)\(n\)번 정점의 자식 정점 중 거리가 \(i\) 이하인 정점의 개수로 정의하여 전처리를 할 수 있다.

이제 특정 정점 \(p\)와 거리가 \(K\) 이하인 정점의 개수를 구할 수 있다.

먼저 \(p\)의 자식 정점 중 거리가 \(K\) 이하인 것은 \(dp[n][K]\)로 바로 구할 수 있다.

이제 \(p\)의 부모 정점인 \(p_1\)의 자식 정점을 고려해보자. 이 경우에는 \(p\)의 부모 정점과 거리가 \(K\) 이하인 것을 구해야 하는데, \(p\)의 자식 정점은 모두 고려해주었으므로, 이를 제외하면, \(dp[p_1][K-1]-dp[p][K-2]\)로 구할 수 있다. 이를 \(p\)의 부모를 \(K\)개까지 타고 올라가면서 반복하여 모두 더해주면 된다.

dp식 전처리의 시간 복잡도는 \(O(NK)\)이고, \(N\)개의 정점에 대해 거리가 \(K\)이하인 정점의 개수 구하는 과정을 각각 \(O(K)\)에 처리할 수 있으므로, 총 시간복잡도는 \(O(NK)\)이다.

K. 꿀벌 승연이

문제 설명

각 칸이 6각형인 2차원 배열모양 꿀벌 집과, 이동할 수 없는 빈 칸이 주어진다. \((1, 1)\)에서 \((N, M)\)으로 이동하는 경우의 수를 출력해야 한다.

알고리즘

각 칸이 4각형인 경우에는 \(dp[r][c] = dp[r][c-1] + dp[r-1][c]\)로 바로 계산할 수 있다. 빈 칸의 경우에는 \(dp[r][c]=0\)으로 처리하면 된다.

각 칸이 6각형인 경우에도 비슷하게 풀 수 있다. 각 칸마다 이동할 수 있는 칸을 보고 점화식을 풀어 해결할 수 있다. 이동할 수 있는 칸이 열 번호의 홀짝에 따라 달라지므로 이를 주의해서 풀면 된다.

L. Calculate! 3

문제 설명

크기가 \(N\)인 간선에 가중치 있는 트리가 주어진다. 가중치는 항상 1이상 30이하이다.

\(u\)에서 \(v\)까지의 비용을 이동 경로에 있는 모든 간선의 XOR로 정의한다.

총 \(M\)개의 쿼리가 주어진다. 각 쿼리는 간선 하나의 가중치를 변경하거나 거리가 \(c\)인 경로의 개수를 출력하는 것 중 하나이다.

알고리즘

오일러 경로 테크닉 + lazy 세그를 활용해야 하는 문제이다.

오일러 경로 테크닉과 lazy 세그를 활용하면 특정 정점을 루트로 하는 서브트리의 모든 정점 update를 \(O(logN)\)에 수행할 수 있다.

트리의 루트를 1로 잡은 뒤, 간선에 가중치를 주는 대신 간선에 연결 된 두 정점 중 자식 정점의 서브 트리에 있는 모든 정점 가중치를 XOR한다. 이렇게 한다면 각 쿼리는 경로가 \(c\)인 경로의 개수가 아니라 가중치를 XOR해서 \(c\)인 정점 쌍의 개수를 출력하는 문제로 바뀌게 된다.

단순히 각 정점의 XOR 결과만 처리한다면 가중치가 \(c\)인 정점의 개수를 구할 수 없다. 다행히도 가중치가 30 이하이기 때문에 XOR을 하더라도 그 결과는 항상 31 이하이다. 따라서 lazy 세그 트리의 각 구간에서 가중치가 0인 정점 개수, 가중치가 1인 정점 개수, ... 가중치가 31인 정점 개수를 모두 저장하여 update를 할 수 있다.

처음에는 모두 가중치가 0인 것으로 처리하였기 때문에 세그 트리의 각 정점은 가중치가 0인 정점 개수는 구간의 크기가 되고, 나머지 정점 개수는 0으로 처리하였다. 초기에도 가중치가 있지만, 이를 맨 처음이 간선 가중치를 변경하는 쿼리가 들어오는 것처럼 처리하였다.

update 쿼리가 들어오면, XOR을 하였을 때 정점의 개수가 어떻게 변하는 지를 계산해주어 처리하면 된다. 

출력하는 쿼리가 들어오면 세그 트리의 루트 노드에서 가중치 별 정점 개수를 알 수 있기 때문에 XOR결과가 \(c\)가 되는 두 가중치를 모두 고려하여 구할 수 있다. 두 가중치의 각 정점 개수의 곱을 모두 더한 것이 쿼리의 정답이 된다.

총평

A, B는 단순 구현 문제이므로 pass

C번은 실버 문제였음에도 생각을 요구해서 실버급 문제도 재미있게 낼 수 있구나라는 걸 느꼈다.

대부분 문제들은 뭔가 어디서 본 거 같은데 조금씩, 또는 꽤 많이 꼬아서 내면서 PS를 많이 해 본 사람들은 웰노운이라고 할 수도 있겠지만 PS를 경험해 본적이 별로 없는 참가자들 입장에서는 흥미로운 문제들이었던 거 같다.