그동안 중앙대학교 알고리즘 학회 ChAOS에 소속되어 백준 온라인 저지에 대회 문제를 출제해보는 귀중한 기회를 몇 번 가졌었는데, 그동안 생각해보니 대회 에디토리얼 이외에 블로그에 문제에 대한 이야기를 한 적이 없었네요. 마침 생각난 김에 그동안 출제했던 문제의 출제 의도를 하나씩 풀어보려고 합니다. (정해 코드는 없습니다!)

글 작성 이후에도 dlaud5379 명의로 다른 문제를 출제할 때마다 업데이트할 예정입니다.

CPC 2020

2020 중앙대학교 프로그래밍 경진대회에 한 문제를 출제하고, 두 문제에 삽화를 제공했습니다.

20210번 "파일 탐색기" (F번)

문제

Windows의 파일 탐색기를 보면 파일이 정렬된 방식이 보통의 정렬 방식과는 다른 것을 알 수 있다. 보통 문자열을 정렬할 때는 맨 앞부터 한 글자씩 비교하다가 어느 한쪽이 끝나거나 일치하지 않는 글자가 있으면 그 위치의 문자를 비교한 결과가 문자열 전체를 비교한 결과가 된다. 한편 파일 탐색기는 여러 자리의 수를 한 글자로 취급해서 비교하는데, 이 때문에 "str12ing"과 "str123ing" 중 후자가 아니라 전자가 앞에 온다. 이러한 정렬 방식을 종종 "natural sort"라고 하기도 한다. 여러 개의 문자열이 주어지면 natural sort 방식으로 정렬한 결과를 출력하는 프로그램을 작성해 보자. 이 문제에서 구현할 알고리즘은 다음을 만족해야 한다.

1. 문자열은 알파벳 대소문자와 숫자로만 이루어져 있다.
2. 숫자열이 알파벳보다 앞에 오고, 알파벳끼리는 AaBbCc...XxYyZz의 순서를 따른다.
3. 문자열을 비교하는 중 숫자가 있을 경우 그 다음에 오는 숫자를 최대한 많이 묶어 한 단위로 비교한다. 예를 들어 "a12bc345"는 "a", "12", "b", "c", "345"의 다섯 단위로 이루어져 있다.
4. 숫자열끼리는 십진법으로 읽어서 더 작은 것이 앞에 온다. 이때 예제 2에서와 같이 값이 \(2^{63}\)을 초과할 수 있다.
5. 같은 값을 가지는 숫자열일 경우 앞에 따라붙는 0의 개수가 적은 것이 앞에 온다.

입력

첫 줄에 문자열의 개수 N(2 ≤ N ≤ 10,000)이 주어진다. 그 다음 N줄에 정렬할 문자열이 한 줄에 하나씩 주어진다. 모든 문자열의 길이는 100 이하이며, 알파벳 대소문자와 숫자로만 이루어져 있다.

출력

N줄에 걸쳐 문제에서 설명한 대로 문자열을 정렬한 결과를 출력한다.

예제 입력 1

8
Foo1Bar
Foo12Bar
Foo3bar
Fo6Bar
Foo00012Bar
Foo3Bar
foo4bar
FOOBAR

예제 출력 1

FOOBAR
Fo6Bar
Foo1Bar
Foo3Bar
Foo3bar
Foo12Bar
Foo00012Bar
foo4bar

예제 입력 2

5
1234567890123456789012345678901234500500
1234567890123456789012345678901234500000
1234567890123456789012345678901234506000
1234567890123456789012345678901234500002
1234567890123456789012345678901234530000

예제 출력 2

1234567890123456789012345678901234500000
1234567890123456789012345678901234500002
1234567890123456789012345678901234500500
1234567890123456789012345678901234506000
1234567890123456789012345678901234530000

2024년 2월 8일 현재 이 문제의 난이도는 골드 2이며, 알고리즘 분류는 #구현 #정렬 #문자열입니다. 출제 이후 거의 4년이 지난 지금 구글에 백준 20210으로 검색해 봤더니 생각보다 이 문제에 대한 블로그 글이 많네요. 풀어주셔서 감사합니다 🙇

지문에서 짐작할 수 있듯이 표준 라이브러리에서 제공하는 정렬 함수에 비교 함수를 만들어 호출하면 되는 정직한 문제입니다. 물론 그 비교 함수 구현이 좀 복잡하긴 합니다. 비교 함수의 조건을 간단하게 요약하면 이렇습니다.

• 숫자는 무조건 문자보다 작다.
• 문자끼리 비교
  • 대소문자 구분 없이 사전순으로 비교하고,
  • 같은 문자라면 대문자가 소문자보다 작다.
• 숫자끼리 비교
  • 최대한 긴 숫자열로 묶는다.
  • 십진법으로 읽은 값으로 비교하고,
  • 같은 값이라면 불필요한 0이 적을수록 작다.

제가 의도한 C++14 풀이(정답자만 열람 가능합니다)에서 비교 함수의 전체적인 구조는 이렇습니다. 입력 문자열의 길이 \(n\)에 대해 비교 함수의 시간 복잡도는 \(O(n)\)입니다.

// 좌변이 작으면 음수, 우변이 작으면 양수, 같으면 0
int 문자끼리_비교(char 좌변, char 우변) {
	if(대문자로 변환한 좌·우변이 다름)
		return (대문자로 변환한 좌변이 다르면 -1, 아니면 1);
	return (좌·우변의 대문자 여부만 추출해서 비교);
}

// 좌변이 우변 미만이어야 `true`
bool 비교함수(const string &좌변, const string &우변) {
	while(좌·우변을 첫 글자부터 스캔하면서) {
		if(우변이 일찍 끝남)
			return false;
		if(좌변이 일찍 끝남)
			return true;
		
		if(좌·우변의 숫자/문자 여부가 다름)
			return (좌변이 숫자인지 여부);
		if(좌·우변이 문자) {
			// 문자끼리 비교
			int 비교결과 = 문자끼리_비교(현재 좌·우변에서 스캔하는 글자);
			if(비교결과 != 0)
				return 비교결과 < 0;
		} else {
			// 숫자열끼리 비교

			// 값으로 비교
			if(좌·우변에서 불필요한 0을 뺀 길이가 다름)
				return (불필요한 0을 뺀 좌·우변의 문자열 길이끼리 비교);
			int 비교결과 = (불필요한 0을 뺀 좌·우변을 사전식으로 비교);
			if(비교결과 != 0)
				return 비교결과 < 0;
			// 불필요한 0의 개수로 비교
			if(좌·우변의 불필요한 0의 개수가 다름)
				return (좌·우변의 불필요한 0의 개수로 비교);
			// 두 숫자열이 일치함
		}
	}
}

CHAC 2022

ChAOS Hello 2022 Algorithm Content에 두 문제를 출제하고, 세 문제에 삽화를 제공했습니다.

CPC 2020에 문제를 출제할 때 지문에 "잇창명"을 넣지 않은 게 후회되어서 이번에 출제하는 두 문제에는 모두 "잇창명"을 넣었습니다.

24390번 "또 전자레인지야?" (D번)

문제

잇창명의 집에는 오래된 전자레인지가 있다. 백준 온라인 저지에서 문제를 너무 많이 푼 잇창명은 문득 이런 궁금증이 생기기 시작했다.

버튼을 최소 몇 번 눌러야 조리시간 2분을 맞출 수 있을까?

잇창명의 전자레인지에는 다음과 같이 버튼이 4개 있고, 각 버튼을 누르면 다음과 같이 작동한다. 초기 상태에는 조리시간이 0초이고, 조리 중이 아니며, 조리시작 버튼을 눌러야 조리가 시작된다.

• 10초: 조리시간이 10초 늘어난다.
• 1분: 조리시간이 1분(60초) 늘어난다.
• 10분: 조리시간이 10분(600초) 늘어난다.
• 조리시작
  • 조리 중이 아닐 때: 조리가 시작된다. 만약에 조리시간이 0초였다면 30초로 늘어난다.
  • 조리 중일 때: 조리시간이 30초 늘어난다.
• 모든 버튼은 조리 중인지의 여부와 무관하게 항상 누를 수 있으며, 별도의 언급이 없을 경우 항상 같은 동작을 한다.

예를 들어 이 전자레인지로 2분을 맞추려면 조리시작 버튼을 4번 누르면 되지만, 최적의 방법은 아니다. 그 대신 1분-1분-조리시작 순서로 버튼을 누르면 버튼을 누른 횟수가 3번이 되어 최적이다. 1분-1분의 경우에는 조리가 되지 않기 때문에 최적이 아니다. 실제로는 조리 중에는 남은 조리시간이 계속 줄어들고 중간에 조리를 취소할 수 있지만, 이 문제에서는 생각하지 않기로 한다.

잇창명은 지난 한 학기 동안 전자레인지를 이용할 때마다 매번 문제로 내고 싶은 마음이 들어서 괴로워하고 있다. 잇창명을 도와주자!

입력

첫 줄에 잇창명이 원하는 조리시간이 M:S 형태로 주어진다(0 ≤ M ≤ 60, 0 ≤ S ≤ 59). M은 분, S는 초이며, 항상 두 자리 숫자로 주어진다.

조리시간은 10초 이상 60분(3600초) 이하이며, 항상 10의 배수이다.

출력

주어진 조리시간을 맞추기 위해 버튼을 눌러야 하는 최소 횟수를 출력한다.

예제 입력 1

02:00

예제 출력 1

3

2024년 2월 8일 현재 이 문제의 난이도는 실버 1이며, 알고리즘 분류는 #너비 우선 탐색 #다이나믹 프로그래밍 #그래프 이론 #그래프 탐색 #그리디 알고리즘입니다.

처음 출제했을 때는 탐욕법과 너비 우선 탐색만을 정해로 생각했는데, 문제 검수 중에 동적 계획법으로 풀 수 있다는 것을 알게 되어 결과적으로는 정해가 사실상 3개인 문제가 되었습니다. 개인적으로 좋은 문제가 되었다고 생각해 꽤 만족스럽네요.

너비 우선 탐색

가장 직관적으로 떠오를 만한 풀이입니다. 조리시간(int)과 조리 여부(bool)의 순서쌍을 정점으로, 각 버튼마다 가능한 상태 변화를 유향 간선으로 삼고 \((0, \mathrm{false})\) 노드에서 출발하는 너비 우선 탐색을 할 수 있습니다.

탐욕법

제가 처음 의도했던 C11 풀이이기도 합니다(정답자만 열람 가능합니다). 당시 Gather에서 공개했던 에디토리얼에 탐욕법에 대한 증명을 실었었는데, 대중에 공개된 링크를 못 찾겠네요. 이 블로그에는 좀 더 엄밀하게 다듬은 증명을 싣겠습니다.

30초 버튼의 특수한 성질을 무시하고 문제를 풀면 30초 버튼을 정확히 0번 혹은 1번 누를 수 있습니다(30초 다음 단위가 60초이므로).

• 30초 버튼을 1번 누르는 경우: 30초 버튼을 가장 처음에 누르면 정상적으로 30초가 추가되면서 조리가 시작되므로 일반적인 탐욕법과 같은 해를 가집니다.
• 30초 버튼을 누르지 않는 경우: 이때는 조리가 시작되지 않으므로 어떻게든 30초 버튼을 추가로 눌러야 합니다. 편의상 추가로 버튼을 누르는 횟수를 \(n\)이라고 하겠습니다.
  • 모든 경우에 대해 \(n=1\)인 알고리즘이 존재합니다.
    • 모든 버튼을 누르고 나서 30초 버튼을 마지막에 추가로 누를 수 있는데, 아직 조리가 시작되지 않았으므로 조리가 시작되고 원래 조리시간이 0이 아니었으므로 조리시간은 유지됩니다.
  • 탐욕법의 성질에 의해 \(n \le 0\)일 수는 없습니다.
  • 위의 논리에 의해 일반적인 탐욕법으로 구한 해에 \(n=1\)을 더한 것이 해가 됩니다.

추가로 입력 범위가 작은 것을 이용해 너비 우선 탐색 코드와 탐욕법 코드가 모든 입력에 대해 같은 출력을 하는지 체크하는, 말 그대로 "proof by AC"¹를 했습니다.

동적 계획법

위의 너비 우선 탐색 풀이를 그대로 동적 계획법으로 바꿀 수 있습니다. 조리시간 i와 조리 여부 j에 대해 dp[i][j]를 만들고 풀면 됩니다.

24394번 "123456789점" (G번)

문제

잇창명은 취미로 리듬 게임을 한다. 위에서 내려오는 노트를 정확한 타이밍에 처리하면 높은 점수를 얻을 수 있다.

노트를 처리하면 각각 다음 판정 중 하나를 받을 수 있다.

• Perfect
• Great
• Good
• Miss

노트를 처리하지 못하면 Miss 판정을 받는다. 위 4가지 판정 이외에 다른 판정은 없다. 노트가 N개 있는 곡에서 Perfect 판정을 a개, Great 판정을 b개, Good 판정을 c개 받았을 때의 점수는 다음 식으로 계산한다. 소숫점 아래는 버린다.

\(\biggl\lfloor {10^9 \times \frac{2a + 2b + c}{2N} + a} \biggr\rfloor\) 

다시 말해, Good 판정의 점수인 \(\frac{10^9}{2N}\)을 기준으로 각 판정의 점수는 다음과 같다.

• Perfect = 2 Good + 1
• Great = 2 Good
• Good = 1 Good
• Miss = 0

예를 들어 노트가 100개 있는 곡에서 Perfect를 10개, Great를 20개, Good을 30개 받으면 450,000,010점을 획득한다. 이때 최고 점수는 Perfect 판정만을 N개 받았을 때 \(10^9 + N\)점이 된다.

잇창명은 이 게임에서 정확히 123,456,789점을 획득해 사람들을 놀라게 하고 싶다. 잇창명은 초고수 플레이어라서 모든 노트의 판정을 원하는 대로 조절할 수 있다. 잇창명이 연주하려는 곡의 노트 수가 주어질 때, 잇창명이 이 곡을 어떻게 연주해야 원하는 점수를 획득할 수 있을지 계산하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 2,000)가 주어진다. 다음 줄부터는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스에서는 한 줄에 노트의 개수 N(1 ≤ N ≤ 20,000)과 잇창명이 원하는 점수 S(0 ≤ S ≤ 109+N)가 공백으로 구분되어 주어진다. N과 S는 정수이다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 다음을 출력한다.

• 잇창명이 Perfect 판정을 a개, Great 판정을 b개, Good 판정을 c개 받아서 정확히 S점을 획득할 수 있다면 2a+2b+c와 a를 공백으로 구분하여 출력한다. 가능한 (2a+2b+c, a)의 쌍이 여러 개인 입력은 없다.
• 잇창명이 곡을 어떻게 연주해도 정확히 S점을 획득할 수 없다면 -1을 출력한다.

예제 입력 1

3
1000 1000001000
4318 899954000
20000 123456789

예제 출력 1

2000 1000
7772 318
-1

2024년 2월 8일 현재 이 문제의 난이도는 골드 3이며, 알고리즘 분류는 #수학입니다. 원래 \(O(T)\)를 의도한 문제라서 난이도 의견에 "\(O(TN)\)이 [출제자의] 의도"라는 말을 보고 깜짝 놀랐습니다.

소재와의 연관성

제가 남긴 solved.ac 난이도 의견에서 볼 수 있듯이 이 문제의 소재는 실존하는 리듬 게임인 Arcaea, 특히 점수 체계입니다. 특히 문제에서 제시한 판정 체계는 실제 게임의 판정 체계를 더욱 대중적인 용어로 바꾼 것입니다.

• Perfect = Shiny PURE
• Great = Early/Late PURE
  • 인게임에서는 기본적으로 세 판정이 모두 PURE로만 표시되며, Early/Late PURE는 따로 표시하도록 하는 숙련자용 설정이 있습니다.
• Good = FAR
• Miss = LOST

위키 호스팅 사이트인 Fandom에 있는 Arcaea Wiki 중 Scoring 문서에서 이 게임의 점수 체계를 확인해볼 수 있는데, 이 역시 최고 점수(10,000,000점)를 제외하고 문제에서 제시하는 것과 일치합니다.

• Shiny PURE = 100% + 1점
  • 이때 100%는 최고 점수를 노트 수로 나눈 것을 기준으로 합니다.
• Early/Late PURE = 100%
• FAR = 50%
• LOST = 0%
• 콤보는 점수에 전혀 영향이 없습니다. 문제에서도 혼동을 피하기 위해 콤보와 관련된 언급을 일절 하지 않았습니다.

원래는 문제에서도 최고 점수를 10,000,000점으로 두었지만, 범위가 너무 작아서 의도치 않은 풀이를 허용할 수 있다는 검수진의 의견을 수용해 1,000,000,000점으로 늘렸습니다.

마지막으로 같은 문서의 Trivia 문단에는 다음과 같은 언급이 있습니다(원문에 없는 강조를 추가했습니다).

• 채보²에 충분한 수의 노트가 있을 경우, 이론적으로는 Pure Memory³ 없이도 10,000,000점 이상을 획득하는 것이 가능하다.
  • 예를 들어, 노트가 2,500개 있는 채보에서 2,499 Shiny PURE + 1 FAR를 받으면 10,000,499점이 된다.
  • 최소 \(\lceil 0.5 \times \left( 1 + \sqrt{\left( 2 \times 10,000,000 \right) + 1} \right) \rceil = 2237\)개의 노트가 필요하다. 현재 최대 콤보가 2237 이상인 채보가 없으므로 이는 불가능하다.

이 서술에서 문제의 정해에 대한 힌트를 얻었습니다. 오래 전에 트위터에서 다른 리듬 게임인 Cytus를 소재로 목표 점수를 입력하면 그 점수를 정확히 맞추는 플레이를 출력하는 콘솔 프로그램을 봤던 것도 어느 정도 영향이 있었습니다.

다 쓰고 나서 Arcaea라는 배경지식을 지우니 "그게 뭔데" 싶은 문제가 되어버렸고, 구글 검색이나 solved.ac 난이도 기여에서도 "문제의 의도를 모르겠다"는 반응이 어느 정도 보여서 정말 아쉽습니다. 노트 개수 제한을 20,000이 아니라 22,361로 뒀으면 의도가 더 드러났을까 싶네요.

출제자가 의도한 풀이

먼저 출력 설명의 "가능한 (2a+2b+c, a)의 쌍이 여러 개인 입력은 없다"와 바로 위에서 언급한 "[\(N\)을] 22,361로 뒀으면 의도가 더 드러났을까 싶네요"에 주목해야 하는데, 22,361은 위에서 제시한 2,237과 수상하게 비슷해 보이는 데서 알 수 있듯이 올 퍼펙트를 해야 1,000,000,000점을 달성할 수 있는 최대 노트 수입니다. 이게 풀이랑 무슨 관련이 있냐고요?

문제에서 Good 판정을 일종의 단위로 사용한 것이 또 하나의 힌트가 되는데, 최종 점수 식을 다음과 같이 두 부분으로 분리할 수 있습니다.

• \(10^9 \times \frac{2a + 2b + c}{2N}\) (Good 단위/"큰 단위")
• \(a\) ("작은 단위")

모든 점수를 \(a \; \mathrm{Good} + b\)로 적고 \(a\)를 특정한 값으로 고정했을 때 가능한 점수의 집합을 "띠"라고 합시다. 그러면 주어진 조건 내에서 서로 다른 어떤 띠끼리도 겹치지 않는다는 것을 알 수 있습니다.

더욱 부연 설명을 하자면, 큰 단위의 점수가 \(a\)일 때 (작은 단위의 점수를 받을 수 있는 유일한 판정인) Perfect의 최대 개수는 \(\lfloor \frac{a}{2} \rfloor\)입니다. 여기서 이 띠가 가질 수 있는 작은 단위의 범위가 \(0 \le b \le \lfloor \frac{a}{2} \rfloor\)이 됨을 알 수 있습니다.

그런데 1 Good = \(\frac{10^9}{2N}\)이므로 작은 단위의 범위가 이 값을 넘어가면 띠끼리 겹치는 상황이 생깁니다. 문제의 범위를 대입하면 1 Good = 25,000, \(\lfloor \frac{a}{2} \rfloor \le 10000\)이므로 그런 일은 발생하지 않습니다. 그래서 이게 풀이랑 무슨 관련이 있냐고요?

이제 띠끼리 겹치지 않는다는 사실을 알았으니 점수의 작은 단위를 신경쓰지 않고 큰 단위를 먼저 구할 수 있고, 그 다음에 작은 단위를 구할 수 있습니다. 가능한 큰 단위는 최대 하나뿐이므로 테스트 케이스당 \(O(1)\)에 답을 구할 수 있습니다.

제가 의도한 C11 풀이(정답자만 열람 가능합니다)를 보면 사칙연산만을 사용해 큰 단위와 작은 단위를 하나씩 구하고, 점수가 띠 안에 들어가는지 확인하는 로직 한 번으로 테스트 케이스가 끝나는 것을 볼 수 있습니다.

아무튼 정해가 배배 꼬인 것도, 힌트가 너무 꽁꽁 숨겨져있던 것도 부정할 수는 없을 것 같습니다. 출제를 하면서 #애드 혹을 붙일지 말지 고민했는데, 지금 알고리즘 분류를 봐도 의외로 애드 혹은 없네요.

여담

문제에 나온 것과 같이 실제로 저도 취미로 리듬 게임을 하고(Arcaea 외에도 다양한 게임을 하고, 지금은 A Dance of Fire and Ice를 가장 자주 합니다), "정확히 123,456,789점을 획득해 사람들을 놀라게 하고 싶"은 생각도(생각만) 가끔씩 합니다. 당연히 실제 잇창명은 모든 노트의 판정을 원하는 대로 조절할 수 있는 초고수 플레이어가 아닙니다.

여담

물론 문제 출제에서도 보람을 느끼고 있지만, 삽화 작업에서도 꽤 보람을 느끼는 편입니다(일단 삽화는 눈에 바로 보이는 편이니까).

위에 언급된 대회의 삽화 중에 뭔가 은근히 귀엽고 나눔스퀘어라운드(이 블로그의 제목체입니다)가 보이면 제 작업물이라고 생각해 주세요. 특히 CHAC 2022의 모든 삽화는 제가 그렸습니다. 😜

오랜만에 생각났으니까 올려봐야지

제가 대학교 프로그래밍 대회 운영진으로 참가하면서 그렸던 귀여운 삽화를 봐주세요. pic.twitter.com/1XkCQGcGhf

— 잇창명 EatChangmyeong💕 (@EatChangmyeong) October 16, 2023

1. 직역하면 "맞았습니다!!에 의한 증명". 알고리즘의 엄밀한 증명이 필요한 프로그래밍 문제에서, 엄밀한 증명 없이 제출해 AC(Accepted; 백준 온라인 저지의 맞았습니다!!에 해당하는 채점 결과)를 받은 것을 "증명"으로 취급하는 농담. ↩

2. Chart. 특정한 악곡의 특정한 난이도에서 등장하는 노트의 배열. 나무위키에서 사용하는 번역어와 의미를 그대로 사용하였다. ↩

3. 특정한 채보에서 모든 노트를 Shiny 여부와 상관 없이 PURE로 처리하면 받는 칭호 ↩