• 대회 풀이
  • 쇼미더코드: 원티드 주관 코딩테스트 대회 2022년 1회차

쇼미더코드: 원티드 주관 코딩테스트 대회 2022년 1회차

A번 - 물약 구매

$N$종류의 물약을 모두 구매하려고 하고, 각 물약에는 번호가 매겨져 있습니다. $i$번째 물약의 가격은 동전 $c_i$개이고, 이 물약을 구매하면 $p_i$종류의 다른 물약의 가격이 내려갑니다.

문제에도 나와 있듯이 물약을 구매하는 순서에 따라 전체 물약을 구매하는 비용이 달라질 수도 있습니다. 따라서, 이 문제는 물약을 구매하는 순서를 정하고, 그 다음 물약을 구매하는 비용을 구해야 합니다.

물약의 개수는 $N$개이고, $N$개를 구매하는 순서는 $O(N!)$개가 있습니다. 순서가 결정되면, 이 순서대로 물약을 구매하는 비용을 계산해야 합니다. 각각의 물약을 구매할 때마다, 할인 정보를 이용해서 다른 물약의 비용을 다시 계산해야 합니다. 물약의 할인 정보는 최대 $N-1$개이기 때문에, 물약 하나의 비용을 계산하는데 $O(N)$이 걸립니다. 총 $N$개 물약의 비용을 계산해야 하기 때문에, 전체 물약의 비용을 계산하는데는 $O(N^2)$이 걸립니다. 따라서, 총 $O(N! \times N^2)$이고, $N ≤ 10$이기 때문에 문제의 시간 제한 안에 해결할 수 있습니다.

코딩할 때 물약의 가격이 $0$이하로 내려가지 않는다는 점을 주의해서 구현해야 합니다.

$N$개의 순서를 결정하려면 재귀 호출을 이용하거나, C++의 경우 next_permutation, Python은 itertools.permutations을 사용해도 됩니다.

소스 1

먼저, 문제에서는 물약의 번호를 $1$부터 $N$까지로 정의했지만, 소스에서는 $0$부터 $N-1$까지로 바꿔서 문제를 해결했습니다. 따라서, 할인되는 물약 번호를 입력 받을때 $-1$로 번호를 1 빼주었습니다.

소스의 각 변수는 다음을 의미합니다.

  • n: 물약의 개수 ($N$)
  • c[i]: i번 물약의 가격 ($c_i$)
  • d[i]: i번 물약을 구매했을 때, 할인되는 다른 물약의 정보를 담고 있는 배열/리스트
    • d[i][j]: $(a_j, d_j)$가 저장되어 있음
  • order[index]: index번째로 구매할 물약의 번호

재귀 함수 go(index)index번째로 구매할 물약의 번호를 정하는 역할을 합니다. 따라서, 모든 물약에 대해서 아직 구매하지 않은 물약을 찾고, 이를 구매했다고 한 다음 index+1번째 구매할 물약을 찾기 위해 재귀 호출을 수행합니다.

index == n이면 모든 물약의 구매 순서를 정한 것이기 때문에, 정한 순서대로 물약 구매 비용을 계산해봅니다.

소스 2

소스 2는 소스 1의 재귀 함수를 언어에서 제공하는 함수를 이용한 것입니다. C++은 next_permutation을 이용했고, Python은 itertools.permutations를 사용했습니다. Java는 언어에서 제공하는 함수가 없어 구현하지 못했습니다.

A번 - 물약 구매 (다른 풀이)

비트마스크를 이용한 다이나믹 프로그래밍으로도 이 문제를 해결할 수 있습니다. $O(2^N \times N^2)$에 해결할 수 있습니다.

B번 - 숫자 이어 붙이기

같은 집을 두 번 방문하지 않을 경우 그 경로는 유일하다는 조건이 있기 때문에, $x_i$번째 집에서 시작해서 $y_i$번째 집까지 이동하는 경로를 찾는 알고리즘은 DFS 또는 BFS입니다. 그 이유는 DFS와 BFS가 한 정점에서 시작해서 연결된 모든 정점을 방문하는 알고리즘이기 때문입니다.

따라서, $i$ 놀이에서는 $x_i$번째 집을 시작 정점으로 하는 DFS/BFS 알고리즘을 이용해 $y_i$까지 가는 경로를 찾을 수 있습니다. 이제 그 경로 상에 존재하는 모든 집의 대문에 있는 수를 이어 붙여야 합니다.

두 수를 이어 붙이는 방법은 두 가지가 있습니다.

  1. 두 수를 문자열로 변환한 다음, 이어 붙이고 정수로 변환
  2. 두 수를 적절한 수식을 통해서 이어 붙임

1번 방법은 소스 3과 같이 구현할 수 있습니다.

소스 3

2번 방법을 구현하려면 수가 몇 자리인지 알아야 합니다. 두 정수 $x$와 $y$를 이어 붙일 것이고, $x$의 뒤에 $y$의 자릿수만큼 $0$을 추가한 다음 $y$를 더하면 됩니다. 수 $y$가 $l$자리 수라면 $x$와 $y$를 이어 붙인 수는 $x\times 10^l + y$와 같습니다. 소스 4와 같이 구현할 수 있습니다.

소스 4

두 방법 중 편한 방법을 사용하면 됩니다.

$A_i$는 최대 $10$자리이고, $x_i$번째 집에서 시작해서 $y_i$번째 집까지 이동할 때 이동 경로 상에 있는 집의 최대 개수는 $N$개입니다. $N$은 최대 $1\,000$이니 이어 붙인 수는 최대 $10 \times 1\,000 = 10\,000$ 자리가 됩니다. 이 수는 너무 큰 수이기 때문에, C++, Java에서는 기본 자료형으로 저장할 수 없습니다. Python의 경우에는 저장은 할 수 있지만, 수가 너무 커서 연산이 너무 오래 걸립니다. 이것이 문제에서 $1\,000\,000\,007$로 나눈 나머지를 구하라고 하는 이유입니다.

$(A + B) \text{ mod } C$는 $((A \text{ mod } C) + (B \text{ mod } C)) \text{ mod } C$와 같습니다. 또, $(A \times B) \text{ mod } C$는 $((A \text{ mod } C) \times (B \text{ mod } C)) \text{ mod } C$와 같습니다. 여기서 $\text{mod}$는 나머지 연산입니다.

실제 수가 아닌 나눈 나머지를 구하면 되기 때문에, concat에서 $1\,000\,000\,007$로 나눈 나머지를 구하게 하면 됩니다. $1\,000\,000\,000$과 $1\,000\,000\,000$를 이어 붙인 수인 $10\,000\,000\,001\,000\,000\,000$이 두 수를 이어 붙였을 때 만들 수 있는 가장 큰 수입니다. 이 값은 C++의 long long과 Java의 long범위를 벗어나니 방법 1을 사용하면 올바른 값을 구할 수 없습니다. 따라서, 방법 2를 사용했습니다.

소스 5

문제에서는 집의 번호를 $1$부터 $N$까지로 정의했지만, 소스 5는 $0$부터 $N-1$까지로 바꿔서 구현했습니다.

소스의 각 변수는 다음을 의미합니다.

  • n: 집의 개수 ($N$)
  • q: 놀이를 한 횟수 ($Q$)
  • d[i]: i번 집 대문에 쓰여 있는 수 ($A_i$)
  • a[i]: i번 집과 도로 통해 연결된 집의 배열/리스트 (인접 리스트)

각각의 놀이마다 BFS 알고리즘을 수행했습니다.

concat의 시간 복잡도는 $O($수의 자릿수$)$입니다. BFS는 모든 정점을 한 번씩 방문하는 알고리즘이기 때문에, 시간 복잡도는 $O(N)$입니다. 하지만, 정점을 방문할 때마다 concat이 한 번씩 호출되어야 합니다. 따라서, bfs 함수의 시간 복잡도는 $O(N \times $수의 최대 자릿수$)$이고, 수의 최대 자릿수는 10이니 $O(10N) = O(N)$으로 나타낼 수 있습니다.

각각의 놀이 결과를 구하기 위해서 bfs를 한 번 호출합니다. 따라서, 시간 복잡도는 $O(QN)$입니다.

C번 - 나는 정말 휘파람을 못 불어

문제에서 유사 휘파람 문자열을 다음과 같이 정의했습니다.

  • WHEE는 '유사 휘파람 문자열'이다.
  • '유사 휘파람 문자열' 뒤에 E를 붙인 것 또한 '유사 휘파람 문자열'이다.

유사 휘파람 문자열은 W가 먼저 나오고, 그 다음 H, 그리고 E가 2개 이상 등장하는 문자열입니다.

$S$의 $i$번째 문자가 W이고, $j$($i < j$)번째 문자가 H인 경우를 생각해봅시다. $j$번째 문자 오른쪽에 E가 $e$개 있다면, 여기서 찾을 수 있는 '유사 휘파람 문자열'은 몇 개가 있을까요?

E만으로 이루어진 부분 수열의 개수는 $2^e$개입니다. 하지만, 이 부분 수열에는 E가 하나도 없는 경우도 포함됩니다. 또, E는 2개 이상 있어야 하니, E가 하나 있는 경우인 $e$개도 빼야 합니다. 따라서, 여기서 찾을 수 있는 부분 수열은 $2^e - e - 1$개입니다.

이 아이디어를 이용해서 소스 6을 구현했습니다.

소스 6

cnt_e[i]에는 i번째와 그 이후에 등장하는 E의 개수가 들어있습니다. $2^i$의 계산을 매번 하는 것보다 미리 구해놓는 것이 더 효율적이기 때문에, two[i]에 $2^i \text{ mod } 1\,000\,000\,007$을 미리 구해놓았습니다.

s[i]W이고, s[j]H인 모든 (i, j)에 대해서, 위에서 구한대로 찾을 수 있는 모든 부분 수열의 개수를 구했습니다.

나머지 연산의 결과는 항상 음이 아닌 정수인데, 뺄셈이 포함된 경우 음수가 나올 수도 있습니다. 따라서, mod값을 한 번 더하고 나눈 나머지를 구해 음이 아닌 정수가 나오게 했습니다.

E의 개수를 구하는 시간 복잡도는 $O(1)$이지만, ij를 정하는데 필요한 시간이 $O(N^2)$이기 때문에, 소스 6의 시간 복잡도는 $O(N^2)$입니다. $N ≤ 200\,000$이기 때문에, 를 받게 됩니다.

위에서 $S$의 $i$번째 문자가 W이고, $j$($i < j$)번째 문자가 H인 경우 찾을 수 있는 '유사 휘파람 문자열'의 수가 $2^e - e - 1$개라는 사실을 알았습니다. $S$의 $k$번째 문자가 W이고, $k < j$, $i \ne k$인 경우, $S$의 $k$번째 문자가 W, $j$번째 문자가 H인 경우 찾을 수 있는 '유사 휘파람 문자열'의 수도 $2^e - e - 1$개입니다. 따라서, $j$만 알고 있어도, '유사 휘파람 문자열'의 개수를 구할 수 있습니다.

$j$번째 문자의 앞에 W가 w개 있다면, 여기서 찾을 수 있는 '유사 휘파람 문자열'의 개수는 $w \times (2^e - e - 1)$개가 됩니다.

소스 7

$j$만 정하면 되기 때문에, 시간 복잡도는 $O(N)$입니다.

C번 - 나는 정말 휘파람을 못 불어 (다른 풀이)

다이나믹 프로그래밍으로도 해결할 수 있습니다. 시간 복잡도는 $O(N)$입니다.