[BOJ 24886] 백준 24886번 - SKH 문자열

		2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이
A		[BOJ 24883] 자동완성
B		[BOJ 24884] 장작 넣기
C		[BOJ 24885] 주식
D		[BOJ 24886] SKH 문자열
E		[BOJ 24887] 최대한의 휴식
F		[BOJ 24888] 노트 조각
I		[BOJ 24891] 단어 마방진

1. 문제

$24886$. SKH 문자열 (2022 숭고한 연합 알고리즘 콘테스트 D번)

백준 24886번 - SKH 문자열 (https://www.acmicpc.net/problem/24886)

2. 풀이

1. 문자열에서 SKH의 개수를 센다.
2. 남는 문자열에서 SK, KH, SH의 개수를 센다.
3. 남는 문자열에서 S, K, H의 개수를 센다.

위에서 $1, 2, 3$의 순서대로 검사한다면, 위 과정을 아래에 있는 코드처럼 하나로 통일할 수도 있다.

---

이제 개수를 센 문자열들 각각에 $p$개의 $S$, $q$개의 $K$, $r$개의 $H$를 배정해야 한다. 순서는 다음과 같다.

1. SKH는 그 자체로 완성이다.
2. SK에 H를 붙인다. SH에 K를 붙인다. KH에 S를 붙인다.
3. S에 KH를 붙인다. K에 SH를 붙인다. H에 SK를 붙인다.
4. SKH를 붙인다.

1, 2 과정은 이런 식으로 진행된다.

• SKH의 개수만큼 정답에 더한다. $\rightarrow$ ans += SKH
• SK의 개수에 R개의 H를 가능한 많이 붙인다. $\rightarrow$ ans += min(SK, R)
• SH의 개수에 Q개의 K를 가능한 많이 붙인다. $\rightarrow$ ans += min(SH, Q)
• KH의 개수에 P개의 S를 가능한 많이 붙인다. $\rightarrow$ ans += min(KH, P)

다음으로는 3, 4 과정을 수행해야 한다. 이는 한번에 계산된다. 일례로 S에 KH를 붙이는 작업을 수행하려 할때, 가능한 최대 개수는 min(S, KH)이다. 따라서, 0 ~ min(S, KH)까지 모든 경우를 탐색한다.

임의의 $x(0\leq x\leq min(S, KH))$에 대해서, K에 SH를 붙이고 H에 SK를 붙이고 SKH를 붙이는 나머지 과정을 모든 $x$에 대해서 수행한다. K에 SH를 붙이는 것도, H에 SK를 붙이는 것도, 이와 동일하게 수행하여 maximum을 갱신한다.

1, 2 과정에서 구한 답과 3, 4 과정에서 구한 답을 더하면, 최종 답이 도출된다.

3. 채점 결과

4. 회고

두 개씩 붙이는 방법을 생각해내기 어려웠고, 구현도 복잡해서 그 과정에서 WA를 두 번 받았다. 약간의 그리디한 방법이 첨가된 완전탐색인거 같은 느낌을 받았고, 이에 대해서 새롭게 알게 되었다.

5. 코드