23.05.02 - 23.05.03 공부 (1/2)

 
군휴가가 얼마 안 남았던지라, 개인 대회 연습을 좀 해봤다. 현실적으로, 지금 내 수준에서 입상을 노려볼만한 ps/알고리즘 대회는 shake!(경인지역 6개대학 연합 프로그래밍 대회)라는 생각이 들어서 2019 본선, 2020 본선을 쭉 돌아보았다.
 
 

shake! 2019 A번. 패턴

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

17300번: 패턴

단순 구현. 다음의 두 가지 조건에만 유의하면 된다.

• 수열의 어떤 수가 두 번 이상 나타나서는 안 된다.
• 두 점(수열에서 연속)을 연결하는 선분 위에 아직 등장하지 않은 점이 있어서는 안 된다.

첫 번째 조건보다 두 번째 조건을 구현하는 것이 다소 어렵다. 나의 경우에는 약간의 하드코딩을 하는 방식을 택했다.
주의해야 할 점은 (1, 3), (4, 6), (7, 9) (가로 방향) / (1, 7), (2, 8), (3, 9) (세로 방향) / (1, 9), (3, 7) (대각선 방향) 로 총 8종류밖에 되지 않는다. 위와 같은 두 점이 나타났을 때, 그 사이에 있는 점이 이미 나타났는지를 확인하는 방식으로 구현했다.
 
 
 
 

shake! 2019 C번. 흰색으로 만들기

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

17302번: 흰색으로 만들기

현재 이 문제의 티어는 골드1이지만, 애드 혹 문제 특성상 개인별 체감 난이도 편차가 심할 것 같다고 생각한다. 당장 나만 하더라도 골드1인 걸 보고 깜짝 놀랐기 때문에..
 
2번 행동과 3번 행동의 차이점을 주의 깊게 보자. 두 행동의 차이점은 자기 자신을 뒤집느냐(3번), 뒤집지 않느냐(2번)이다. 우선 모든 칸에 대하여 2번 행동을 수행하자. 각 칸에 대하여, 인접한 칸의 2번 행동에 의해 뒤집혀진 횟수를 저장해 놓는다. 어떤 칸의 원래 색이 W(흰색)라면 짝수 번 뒤집혀야 할 것이고, B(검은색)라면 홀수 번 뒤집혀야 할 것이다. 만약 그렇지 않다면 자기 자신을 한 번 더 뒤집으면 된다. 그러한 칸들에 대하여 2번 행동이 아닌 3번 행동을 수행하는 것으로 바꾸어 주면 된다.
 
 
 
 

shake! 2019 F번. 사탕 배달

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

17305번: 사탕 배달

꽤나 고생한 문제. 처음에 DP 풀이에 꽂혀 시간이 많이 소요되기도 했고, 풀이 방식을 깨달은 뒤에도 문제를 잘못 이해하거나 잔잔한 구현 실수를 하기도 했다. 
 
3g 사탕과 5g 사탕을 구분하여 당도를 내림차순으로 정렬한다. 이때 각 사탕 종류에 대하여 당도가 큰 것부터 담는 것이 최선임을 쉽게 알 수 있다. 다음으로, 개수를 결정한다. 담아갈 3g 사탕의 개수와 5g 사탕의 개수를 각각 $x$, $y$라 할 때, 다음의 두 가지 조건을 만족하여야 한다.

• $3x+5y \leq w$
• $x\leq$ (3g 사탕의 개수) && $y\leq$ (5g 사탕의 개수)

이 조건을 만족하는 개수 조합 중에서 당도가 최대인 것을 찾으면 된다.
 
 
 
 

shake! 2019 H번. 색깔 통일하기

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

17307번: 색깔 통일하기

티어를 까지 않고 풀었을 때에는 그렇게 어려워 보였는데, 까고 풀어보니 생각 외로 만만했던 문제. 오직 하나의 버튼만 누르기 때문에 어떤 하나의 버튼을 중심으로 왼쪽 방향과 오른쪽 방향을 구분해서 풀이하면 된다.
 
왼쪽 방향와 오른쪽 방향 각각에 대하여 $l[i]$, $r[i]$를 다음과 같이 정의하자.

• $l[i]$ : 1번 버튼에서 $i$번 버튼까지 모두 동일한 색이 되기 위하여 1번 버튼을 눌러야 하는 횟수
• $r[i]$ : n번 버튼에서 $i$번 버튼까지(역순) 모두 동일한 색이 되기 위하여 n번 버튼을 눌러야 하는 횟수

어떤 버튼의 색 종류 번호가 다음 버튼의 색 종류 번호보다 작을 경우, 그냥 다음 버튼의 색 종류 번호에서 지금 버튼의 색 종류 번호를 빼주면 되지만, 그렇지 않을 경우, 색 종류 $c$를 더해주어야 한다.
예를 들어, $c=3$이고, 1번 버튼의 색이 2, 2번 버튼의 색이 1이라면, 1번 버튼을 $1-2+3=2$번 눌러주어야 1번과 2번 버튼의 색이 동일해진다. 따라서 다음 누적합 과정을 거친다.

• $l[i]=l[i+1] + (arr[i] - arr[i+1] \geq 0\ ?\ arr[i] - arr[i+1] : arr[i] - arr[i+1] + c)$
• $r[i]=r[i-1] + (arr[i] - arr[i-1] \geq 0\ ?\ arr[i] - arr[i-1] : arr[i] - arr[i-1] + c)$

모든 버튼에 대하여 $max(l[1] - l[i], r[n] - r[i])$ 값을 비교하여 그 값이 최소가 되는 번호를 구하면 된다.
 
 
 
 

shake! 2020 A번. 독서실 거리두기

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

20665번: 독서실 거리두기

그렇게까지 어려운 문제는 아닌데, 사소한 실수 몇 개가 쌓여서 3시간 동안이나 디버깅한 문제.. 문제를 풀어냈을 때의 그 허탈함은 아직도 잊을 수가 없다.
 
문자열로 입력받은 시간을 정수로 전처리한 뒤, 입실 시간이 빠른대로 정렬. 다음부터는 독서실 규칙에 따라 각 인원을 자리에 배치시키면 된다. 어떤 사람의 입실 시간을 st라 하자. st 시점에 사용 중인 독서실 자리를 모두 저장해놓는다(이 배열을 $v$라 하자). 만약 사용 중인 독서실 자리가 없다면 1에 배치한다. 사용 중인 자리가 하나라도 있다면, 이 사람이 앉을 수 있는 자리는 (당연해 보이지만) 1. 1번 자리이거나, 2. n번 자리이거나, 3. 그 중간 자리이다. 

1. $v[0] - 1$이 최대
2. $n - v[v.size()-1]$이 최대
3. 가능한 $i$에 대하여, $(v[i+1] - v[i]) / 2$가 최대, 이때 앉아야 할 위치는 $(v[i+1] + v[i]) / 2$임을 알 수 있다.

물론 앉을 수 있는 위치가 여러 개일 경우 작은 번호가 우선인 경우를 잊지 말아야 한다.
 
 
 
 

shake! 2020 B번. 인물이와 정수

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

20666번: 인물이와 정수

알고리즘 분류에는 '우선순위 큐'라 적혀 있으나 C++의 multiset을 이용한 풀이도 가능하다. 
 
다음의 그리디 풀이가 성립한다. "처음의 난이도와 올라간 난이도를 더한 값들에서 계속해서 가장 작은 값을 빼낸다. 이때 빼낸 값에 대하여 팁이 존재할 경우 팁과 관련된 값은 업데이트한 뒤 다시 multiset에 넣는다." 
최대 난이도만이 정수가 느끼는 게임의 난이도이기 때문에 계속해서 작은 값만을 빼는 것이 최적이다. 어떤 값 $x$, $y$ ($x<y$)에 대하여 $y$를 빼는 것이 최적이라고 하자. 이때의 답은 자명하게 $y$이다(다음으로 빼는 것이 $x$인데 $x<y$이므로). 이때 $y$가 아닌 $x$를 먼저 뺀다고 해서 답이 $y$임은 바뀌지 않는다. 따라서 그리디 구조가 성립한다.
 
팁에 의한 업데이트를 위해서는 multiset에 값뿐만 아니라 각각의 인덱스 또한 넣어야 한다.