Skip to content

BOJ 18766-18771, 19529, 19240-19244, 19592-19597

2021년 1월 15일에 올라온 문제들입니다.

18766 카드 바꿔치기

두 배열을 정렬해서 같은지 판별하면 됩니다.

18767 조교 배치

저는 [[최대 유량]]으로 풀었기 때문에 (...) 출제자님의 풀이를 싣습니다.

brute force + greedy로 가능합니다. A/B/C중 하나만 원하는 사람들은 별 방법이 없으니 먼저 배치하고, AB/BC/CA 원하는 사람들을 A/B/C중 어느 곳에 우선적으로 배치할지에 대해 brute force로 우선순위를 정하고 그에 맞춰서 우선적으로 배치를 하는 식으로 해결 가능합니다 (ABC 모두 가능한 wild card에 해당하는 사람들은 마지막에 자리 남는 곳에 보내버리면 됩니다). max flow가 더 당연한 풀이인데, max flow를 모르더라도 (혹은 brute force만 알더라도) 풀 수 있긴 합니다. 그 외에 조금 다른 풀이가 하나 더 있는데 max flow 아이디어와 크게 다르지 않아서.. 생략합니다.

18768 팀 배정

각 참가자마다 공격과 방어를 결정하는 게 아니라, 모든 참가자를 일단 공격 팀에 넣은 다음 몇 명을 뽑아서 방어 팀으로 데려간다고 합시다. 즉 능력치 합은 A[1] + ... + A[n]에서 시작하고, 참가자 x를 방어 팀으로 데려가면 능력치 합은 B[x] - A[x]만큼 변합니다.

정확히 m명을 방어 팀으로 데려가고자 한다면 전략은 자명합니다. B[x] - A[x] 순으로 정렬한 다음 큰 참가자부터 한 명씩 데려가면 됩니다. 각각의 m에 대해 최대 능력치 합을 구할 수 있으니, "두 팀에 배정된 참가자 수의 차이는 k 이하가 되어야 한다"라는 조건도 똑같이 처리할 수 있습니다.

18769 그리드 네트워크

그냥 MST를 구하는 문제입니다. MST를 구하면 됩니다.

18770 불안정한 물질

이 그래프는 "정점과 간선의 개수가 같은 컴포넌트" 여러 개로 이루어진 그래프입니다. 각각의 컴포넌트에 대해 최댓값을 구해봅시다.

정점과 간선의 개수가 같은 연결 그래프는 사이클 하나에, 각 정점마다 한 개의 rooted 트리가 달려 있는 형태입니다. (사이클에 속한 노드를 루트 노드로 둡시다. 예를 들어 그냥 사이클 하나만 있으면 모든 트리가 정점 한 개인 것으로 볼 수 있습니다.) 사이클을 DFS로 찾고, 사이클의 각 점으로부터 다시 DFS를 해서 트리를 모두 찾읍시다.

각각의 rooted 트리마다, "선택한 노드 중에 루트가 포함될 때 최댓값"이랑 "포함되지 않을 때 최댓값"을 구합니다. 각각 A[v]와 B[v]라고 합시다. 이는 트리에서 하는 다이나믹 프로그래밍 문제로 잘 알려져 있습니다.

그 다음에는, 원 위의 각 점 v마다 A[v] 또는 B[v]를 고르되, A[v]를 연속으로 두 번 고르지 않을 때의 최댓값을 구합니다. 이것도 원에서 하는 다이나믹 프로그래밍 문제로 간단하게 풀 수 있습니다.

18771 오픈소스 버그 잡기

놀랍게도 https://www.acmicpc.net/problem/19579 와 같은 문제입니다. 물론 19579가 공개될 당시에는 18771이 공개되지 않았으므로, 그냥 우연입니다.

  1. 아이템의 부분집합을 선택하되
  2. 특정 아이템을 넣었을 때/넣지 않았을 때 얻는 페널티와,
  3. 특정 아이템 x를 넣고 y를 넣지 않았을 때 얻는 페널티가 주어지고,
  4. 총 페널티를 최소화

하는 문제는 minimum cut을 생각할 수 있습니다. 왜냐하면

  1. 각각의 아이템을 정점 하나로 둡시다.
  2. 특정 아이템 x를 넣었을 때 c의 페널티를 얻는다면, x에서 sink로 가는 가중치 c의 간선을 긋습니다. 넣지 않았을 때 c의 페널티를 얻는다면, source에서 x로 가는 가중치 c의 간선을 긋습니다.
  3. 특정 아이템 x를 넣고 y를 넣지 않았을 때 c의 페널티를 얻는다면, x에서 y로 가는 가중치 c의 간선을 긋습니다.
  4. 이제 source와 sink를 분리하는 최소 컷이 곧 최소 페널티가 됩니다.

각 버그 x마다 정점 x를 만들고, source 정점과 sink 정점을 만듭니다.

  1. 버그 x의 흥미도를 f라고 합시다. 만약 f < 0이라면, 이 버그를 선택하면 |f|의 페널티를 얻습니다. 만약 f > 0이라면, 이 버그를 선택하지 않으면 |f|의 페널티를 얻습니다.
  2. 버그 x를 잡으려면 y를 같이 잡아야 한다고 합시다. 그러면 x를 넣고 y를 넣지 않았을 때 무한대의 페널티를 얻습니다. 물론 진짜로 무한대를 넣을 필요는 없고, 매우 큰 수를 넣으면 됩니다.

이제 위에 서술한 방식으로 간선을 긋고, source에서 sink로 가는 최대 유량을 흘려주면 됩니다.

19529 카드 놀이

SA - SB를 x로 만드는 게 아니라 SA를 y로 만드는 걸 목표로 합시다. y를 구하려면 연립방정식 SA + SB = n(n+1)/2, SA - SB = x를 풀면 됩니다. 그런 y가 없으면 당연히 불가능합니다.

이제 중요한 관찰은, 카드 1은 무조건 N번째 턴에 가져간다는 것입니다. 따라서 카드 1은 가져갈 사람이 이미 정해져 있으며, 양끝 중 한 쪽의 카드가 1이라면 그 다음부터는 한 쪽에서만 계속 카드를 가져갈 것입니다.

그런데 한 쪽에서만 계속 카드를 가져가더라도 별로 큰 제약이 아닌 게, 카드 1을 제외한 나머지를 누가 가져갈지를 마음대로 결정할 수 있습니다. 나머지 카드 중 Alice가 가져갈 카드가 a, b, ..., z라고 합시다. 그러면 한 칸의 공백을 사이에 두고 1, a, b, ..., z를 놓은 다음, Bob이 가져갈 카드를 그 공백에 놓으면 됩니다.

그래서 우리가 풀어야 할 문제는 이렇게 변합니다. 2 이상 N 이하의 서로 다른 정수 중 k개를 골라서 합이 S여야 합니다. 가능한 S의 최솟값과 최댓값은 쉽게 계산할 수 있고, 우리가 원하는 S가 그 범위를 벗어나면 불가능합니다. 그리고 벗어나지 않으면 가능합니다. 왜냐? 이렇게 하면 O(N^2)에 정수 k개를 고를 수 있기 때문입니다.

  1. 먼저, 2, 3, ..., 2+k-1을 골랐다고 합시다.
  2. 2+k-1을 1씩 증가시키다가, 합이 S가 되거나 더 이상 증가시킬 수 없으면 멈춥니다.
  3. 2+k-2를 1씩 증가시키다가, 합이 S가 되거나 더 이상 증가시킬 수 없으면 멈춥니다.
  4. 2+k-3을 ...
  5. ...

위 과정을 그대로 구현하면 O(N^2)이 되지만, 각 단계를 O(1)에 구현할 수 있습니다. 합이 S가 되는 것과 더 이상 증가시킬 수 없게 되는 것 중 어느 순간이 먼저 오는지를 간단한 수식 계산으로 알아내면 됩니다. 이제 O(N)이 되어 문제를 풀 수 있습니다.

19240 장난감 동맹군

그냥 이분그래프를 판별하는 문제입니다. 이분그래프를 판별하면 됩니다.

19241 해적과 보석

먼저, (내 점수 - 상대방 점수)를 최대화하는 게 아니라, 하나의 공통된 점수가 있다고 합시다. 즉 A는 이 점수를 A[x]만큼 올리고, B는 이 점수를 B[x]만큼 내립니다.

그 다음, A와 B가 하나씩 물건을 가져가는 게 아니라, A가 모든 물건을 가진 채로 시작하고 B가 하나씩 빼앗는다고 합시다. 즉 점수는 A[1] + ... + A[n]에서 시작하고, 매 턴마다 A는 하나의 물건을 못 가져가게 확보하고, B는 하나의 물건을 가져간 다음 점수를 A[x] + B[x]만큼 내립니다.

이제 A[x] + B[x] 순으로 정렬한 다음 큰 것부터 하나씩 확보하거나 가져가면 됩니다.

19242 행렬 합

부분행렬의 왼쪽 끝 L과 오른쪽 끝 R을 고정했다고 하면, 각 행은 "그 행의 L번째부터 R번째까지 수의 합"인 하나의 수로 압축됩니다. Prefix sum을 미리 구해놓으면 이를 구할 수 있습니다. 이제 우리가 풀어야 하는 문제는, 배열이 주어졌을 때 합이 x 이하인 부분배열의 개수를 구하는 것이고, O(NlogN)에 풀어야 합니다. 그러면 전체 문제는 O(NM^2logN)에 해결됩니다.

이 배열의 prefix sum을 구하면, PS[r] - PS[l-1] <= x, l <= r인 (l, r)의 개수를 구하는 문제가 됩니다. 다음 두 쿼리를 처리할 수 있으면 됩니다.

  • 집합에 수 y를 추가한다.
  • 집합에 있는 수 중 y 이하인 것의 개수를 출력한다.

만약 집합에 들어갈 수가 0 이상 N 이하 같은 작은 범위라면 펜윅 트리로 풀 수 있습니다. 그런데 실제로는 수가 매우 크기 때문에, 집합에 들어갈 수를 이 범위로 좌표압축을 해줘야 합니다. 시간 제한이 매우 빡빡하기 때문에 비효율적으로 구현하면 TLE를 받을 수 있습니다.

19243 팀 가르기

  1. 아이템의 부분집합을 선택하되
  2. 특정 아이템을 넣었을 때/넣지 않았을 때 얻는 페널티와,
  3. 특정 아이템 x를 넣고 y를 넣지 않았을 때 얻는 페널티가 주어지고,
  4. 총 페널티를 최소화

하는 문제는 minimum cut을 생각할 수 있습니다. 왜냐하면

  1. 각각의 아이템을 정점 하나로 둡시다.
  2. 특정 아이템 x를 넣었을 때 c의 페널티를 얻는다면, x에서 sink로 가는 가중치 c의 간선을 긋습니다. 넣지 않았을 때 c의 페널티를 얻는다면, source에서 x로 가는 가중치 c의 간선을 긋습니다.
  3. 특정 아이템 x를 넣고 y를 넣지 않았을 때 c의 페널티를 얻는다면, x에서 y로 가는 가중치 c의 간선을 긋습니다.
  4. 이제 source와 sink를 분리하는 최소 컷이 곧 최소 페널티가 됩니다.

각 임직원 x마다 정점 x를 만들고, source 정점과 sink 정점을 만듭니다.

  1. 임직원 x의 공격력 A[x]가 방어력 D[x]보다 크다면, x를 넣지 않았을 때 (즉 방어팀에 넣었을 때) A[x] - D[x]의 페널티를 얻습니다. A[x]가 D[x]보다 작다면, x를 넣었을 때 D[x] - A[x]의 페널티를 얻습니다.
  2. 태스크 포스의 페널티가 S이고, 임직원 x1, ..., xk가 속해 있다고 합시다. 그러면 각각의 임직원 쌍 (x, y)에 대해, x를 넣고 y를 넣지 않았을 때 S의 페널티를 얻습니다. x < y와 x > y를 모두 고려해줘야 한다는 점을 유의합시다.

이제 위에 서술한 방식으로 간선을 긋고, source에서 sink로 가는 최대 유량을 흘려주면 됩니다. 실제 최소 컷을 찾으려면, 최종 residual graph에서 source로부터 도달 가능한 정점들을 모두 잡으면 됩니다.

19244 괄호 문자열

DP[l][r] = "l번째부터 r번째까지의 문자만 입력으로 주어졌다고 했을 때, 지워야 되는 문자의 최대 개수"로 둡니다. 우선 DP[i][i] = 1이고, 편의를 위해 l > r일 때 DP[l][r] = 0이라고 합시다.

그 다음에는 l번째 문자가 어떻게 되는지에 따라 케이스를 나눕니다.

  1. l번째 문자를 지운다면, 1 + DP[l+1][r]이 됩니다.
  2. l번째 문자를 k번째 문자와 매칭한다면, DP[l+1][k-1] + DP[k+1][r]이 됩니다. 물론 그렇게 매칭할 수 없는 경우는 제외해야 합니다.

그러면 O(N^3)에 문제를 풀 수 있습니다.

19592 장난감 경주

상대방의 자동차 N-1개 중에서는 가장 빠른 자동차만 중요합니다. 내가 가장 빠르다면 정답은 0입니다. 아니라면 반드시 부스터를 써야 하고, 가장 빠른 자동차의 속력을 v라고 합시다.

수의 범위가 최대 100만이기 때문에, 부스터를 사용하는 가능한 모든 경우를 고려해도 충분합니다. 부스터를 사용해서 B m/s로 간다고 하면, B > X라면 X/B 초가 걸리고, B <= X라면 1+(X-B)/V 초가 걸립니다. 이제 이걸 X/v와 비교하면 됩니다.

19593 다도해

E[i]는 오로지 E[i-1]에 의해서만 결정되기 때문에, E를 N^2번 계산하면 결국에는 사이클을 타게 되어 있습니다. 따라서 N^2번까지 돌려 봤는데도 다 연결이 안 되면 답은 0입니다.

모든 섬을 연결하는 다리를 지었는지 판별하려면 disjoint set을 써서, 합치는 작업이 N-1번 일어났는지 판별하면 됩니다.

19594 슈퍼 컴퓨터

일단 "최우선 처리 대상" 처리를 하지 않았다고 합시다. 그러면 프로그램을 D값에 대한 오름차순으로 정렬하고 그 순서대로 진행하는 것이 최적입니다. 왜냐하면, 현재 프로그램의 D값이 바로 다음 프로그램의 D값보다 크다면, 그 둘의 순서를 뒤바꿔도 최대 페널티는 증가하지 않기 때문입니다.

이제 "최우선 처리 대상" 처리를 했다고 합시다. 그래도 프로그램들의 D값은 안 바뀌니까, 정렬했던 바로 그 순서 그대로 진행하는 것이 최적입니다. 무슨 프로그램에 최우선 처리를 했는지에 따라 모든 경우를 시뮬레이션하면 O(N^2) 알고리즘을 얻습니다.

이제 각각의 경우를 O(1)에 시뮬레이션해봅시다. 최우선 처리를 안 했을 때 각 프로그램 i에 대해 (C[i] - D[i])를 저장해 둡니다. 이 값을 DIFF[i]라고 합시다. 이제 프로그램 x를 최우선 처리했다면, 모든 y >= x에 대해 C[y]가 H[x] - 1만큼 줄어들기 때문에, DIFF[y]도 H[x] - 1만큼 줄어듭니다. 따라서 DIFF의 최댓값은

max(DIFF[1], ..., DIFF[x-1], DIFF[x]-H[x]+1, ..., DIFF[n]-H[n]+1)
= max((1부터 x-1까지 DIFF의 최댓값), (x부터 n까지 DIFF의 최댓값)-H[n]+1)

이제 prefix sum과 같은 방식으로 prefix max를 전처리하고, 같은 방식으로 suffix max도 전처리하면 위 식을 O(1)에 계산할 수 있습니다.

19595 소수 게임

10만 까지의 소수를 다 얻어낸 다음, 각각의 시작 정수에 대해 Bob이 이기는지 아닌지를 DP로 구합니다.

x 이상 x+k-1 이하에 대한 승률을 구하려면 DP[x] + ... + DP[x+k-1]을 구해야 하는데, 이는 DP 배열의 prefix sum S[x] = DP[0] + ... + DP[x]를 전처리해 두면 O(1)에 구할 수 있습니다.

DP를 다 구하고, S도 다 구한 다음에 테스트케이스를 받기 시작하면 테스트케이스 당 O(A)에 풀 수 있습니다.

19596 선물 교환

무방향 그래프의 각 간선에 방향을 주되, 각 정점마다 indegree와 outdegree의 차이가 -1, 0, 또는 1이도록 하는 문제입니다. 정점의 차수가 홀수면 차이는 -1이나 1일 것이고, 짝수면 0일 것입니다.

사이클 하나를 만들면 indegree와 outdegree가 각각 하나씩 늘어나니까, 그래프 전체를 사이클로 덮으면 모든 정점의 in/outdegree 차이는 0일 것입니다. 다행히도 모든 정점의 차수가 짝수면 그래프 전체를 사이클로 덮을 수 있습니다. 방법은 놀랍게도 간단한데, 모든 간선을 쓸 때까지 다음을 반복하면 됩니다.

  1. 간선이 남아있는 정점 a를 아무렇게나 하나 잡는다.
  2. 남아있는 아무 간선이나 써서 다음 정점 b로 이동하고, 그 간선의 방향을 a->b로 준다.
  3. 간선이 안 남아있는 정점 c가 나올 때까지 2번을 반복한다.

그러면 a = c이기 때문에 사이클이 됩니다. 왜냐? 어떤 정점에 도착했는데 더 이상 쓸 수 있는 간선이 없으려면, 도착하기 직전에 남은 간선이 1개여야 합니다. 그런데 그 "도착하기 직전에 남은 간선"의 개수는 a를 제외하면 전부 짝수 개입니다. 따라서 남은 간선이 1개면 그 정점은 a입니다.

이제 모든 차수가 짝수인 경우는 됐고, 차수가 홀수인 정점이 있다고 합시다. 이때는 새로운 정점 N+1을 만들어서, 차수가 홀수인 정점과 N+1을 간선으로 이으면 됩니다. 차수가 홀수인 정점은 짝수 개 존재하기 때문에, 기존에 있던 정점뿐만 아니라 N+1도 짝수 차수가 됩니다. 이렇게 바꾼 그래프에서 위 풀이를 그대로 적용하고, N+1 정점을 도로 지우면 끝납니다.

19597 문자열 뒤집기

조건을 만족하는 리버스 문자열 (이를 "좋은 문자열"이라고 부릅시다) 중 사전순으로 가장 앞서는 것을 찾아야 합니다. 이는 다음 방식으로 찾을 수 있습니다.

  1. 0으로 시작하는 좋은 문자열이 있는지 판별합니다. 있다면, 정답은 0으로 시작합니다. 없다면, 정답은 1로 시작합니다.
  2. 이제 정답의 첫 번째 글자를 알아냈습니다. 그 글자를 A라고 할 때, A0으로 시작하는 좋은 문자열이 있는지 판별합니다. 있다면, 정답은 A0으로 시작합니다. 없다면, A1으로 시작합니다.
  3. 두 번째 글자를 알아냈습니다. B라고 할 때, AB0으로 시작하는 좋은 문자열이 있는지 여부에 따라 마찬가지로 세 번째 글자를 알아냅니다.
  4. 마지막 글자까지 쭉 반복합니다.

A1 A2 ... Ak로 시작하는 좋은 문자열이 있는지 판별하려면 이렇게 하면 됩니다.

  1. 첫 번째부터 k번째까지의 문자열은 뒤집을지 말지가 이미 결정되어 있습니다. 만약 k번째까지 봤는데 사전순으로 정렬되어 있지 않다면, 좋은 문자열이 없습니다.
  2. k+1번째부터는 뒤집을지 말지를 우리가 선택할 수 있습니다. 따라서 두 가지 경우가 생기는데, 두 경우 모두 사전순 정렬 규칙이 깨진다면, 좋은 문자열이 없습니다. 한 경우만 사전순 정렬 규칙이 깨진다면, 다른 한 경우를 선택해야 합니다. 둘 다 규칙이 깨지지 않는다면, 둘 중에서 "현재 보고 있는 단어가 사전 순으로 앞선 경우"를 선택합니다. 그래야 이후 과정에서 선택의 폭이 넓어지기 때문입니다.
  3. 마지막 문자열까지 쭉 반복합니다. 마지막까지 정렬 규칙이 안 깨진다면, 좋은 문자열이 있습니다.

한 번 판별하는 데 O(NS) 시간이 걸립니다. S는 한 문자열의 길이입니다. 이 과정을 N번 반복하므로 전체 O(N^2S)에 문제가 풀립니다. O(N^2 + NS)로 최적화할 수도 있습니다.

전체 O(NS) 시간에 풀리는 그리디 알고리즘도 있었던 것으로 기억하는데 자세히 생각해보진 않았습니다.