CSES Introductory Problems

주변인 몇 명에게 PS를 권유하게 되면서 좋은 초보자용 문제 셋을 찾아다니다 CSES Problem Set을 발견했습니다.

그 중 Introductory Problems 섹션에는 PS를 처음 시작하는 사람들이 풀면 좋을 만한 ABS보다 조금 더 난이도있는 문제들로 이루어져 있었습니다.

이번 포스트에서는 그 풀이와 증명을 적어 보려고 합니다.

Weird Algorithm

$3x + 1$ 로도 알려져 있는 콜라츠 추측과 관련된 문제입니다.

콜라츠 추측

모든 자연수 $n$ 에 대해

$n$ 이 짝수이면 $2$ 로 나누기
$n$ 이 홀수이면 $3$ 을 곱하고 $2$ 를 더하기

를 반복하면 결국 $1$ 이 된다는 추측입니다.

시간 복잡도를 미리 알 순 없지만 직접 코드를 작성해 보면 입력 범위에서 모든 시행 횟수가 $600$ 번이 채 되지 않는다는 것을 알 수 있습니다.

코드 (Python)

n = int(input())
 
while n > 1:
    print(n, end=" ")
 
    if n % 2 == 0:
        n //= 2
    else:
        n = 3 * n + 1
 
print(n)

Missing Number

다양한 방법으로 문제를 해결할 수 있습니다. 집합 자료구조를 사용해도 되고, boolean 배열을 사용해도 됩니다.

저는 $1$ 부터 $n$ 까지의 합에서 입력받은 모든 정수를 빼서 남은 정수를 구하는 방식을 사용했습니다.

코드 (Python)

n = int(input())
 
s = n * (n + 1) // 2
 
for num in map(int, input().split()):
    s -= num
 
print(s)

Repetitions

연속된 같은 알파벳의 개수를 세 주면 됩니다.

코드 (Python)

s = input()
n = len(s)
 
ans = 1
streak = 1
 
for i in range(1, n):
    if s[i - 1] == s[i]:
        streak += 1
        ans = max(ans, streak)
    else:
        streak = 1
 
print(ans)

Increasing Array

$x_i > x_{i + 1}$ 인 경우 $x_{i + 1}$ 을 $x_i$ 보다 더 크게 올릴 필요가 없습니다. 따라서 $x_{i + 1} = x_i$ 로 바꾸는 데 필요한 연산 횟수만 모두 더해 주면 답이 됩니다.

증명

$x_i > x_{i + 1}$ 인 경우에서 $x_{i + 1}$ 을 $x_i$ 보다 크게 증가시켜도 답인 경우가 있다고 가정합시다.

문제의 조건에 따르면 $x$ 가 단조 증가해야 하므로 $j > i + 1$ 인 모든 $j$ 에 대해 $x_i < x_{i + 1} \leq x_j$ 입니다.

따라서 $x_{i + 1}$ 을 $1$ 만큼 덜 증가시켜도 조건에 위배되지 않고, 이 경우가 연산 횟수가 적어도 $1$ 만큼 적으므로 가정이 틀렸습니다.

코드 (Python)

n = int(input())
x = list(map(int, input().split()))
 
ans = 0
 
for i in range(1, n):
    if x[i - 1] <= x[i]:
        continue
 
    ans += x[i - 1] - x[i]
    x[i] = x[i - 1]
 
print(ans)

Permutations

$2$ 부터 시작해서 짝수 $2$ , $4$ , $6$ , $8$ , $\dots$ 를 모두 나열한 후 다시 $1$ 로 돌아와서 홀수 $1$ , $3$ , $5$ , $7$ , $\dots$ 를 순서대로 나열해 주면 됩니다.

예외적으로 $n = 2$ 혹은 $n = 3$ 에서는 해가 존재하지 않으므로 이 부분만 조심하면 됩니다.

코드 (Python)

def main():
    n = int(input())
 
    if 2 <= n <= 3:
        print("NO SOLUTION")
        return
 
    print(*range(2, n + 1, 2), *range(1, n + 1, 2))
 
 
main()

Number Spiral

$1$ 행과 $1$ 열에 적혀있는 수들을 자세히 살펴봅시다.

$1$ 행에는 $1^2,\ 1^2 + 1,\ 3^2,\ 3^2 + 1,\ 5^2,\ 5^2 + 1,\ \dots$ 가 적혀 있습니다.

$1$ 열에는 $0^2 + 1,\ 2^2,\ 2^2 + 1,\ 4^2,\ 4^2 + 1,\ \dots$ 가 적혀 있습니다.

$x$ 와 $y$ 중 더 큰 수를 이용해서 $1$ 행 또는 $1$ 열에서 먼저 수를 찾고, 더 작은 수만큼 이동해서 정답을 계산해 주면 됩니다.

코드 (Python)

홀짝성을 최대한 간결하게 다루기 위해서 비트 연산을 사용했습니다.

y & ~1은 y의 첫 번째 비트를 끄는 동작으로, 가장 가까우면서 작거나 같은 짝수를 찾습니다.

((x - 1) | 1)은 가장 가까우면서 작거나 같은 홀수를 찾습니다.

y & 1과 ~x & 1은 홀짝 판별입니다.

def solve():
    y, x = map(int, input().split())
 
    ans = 0
 
    if y >= x:
        ans = (y & ~1) ** 2 + (y & 1)
        ans += (x - 1) * (1 if y & 1 else -1)
    else:
        ans = ((x - 1) | 1) ** 2 + (~x & 1)
        ans += (y - 1) * (1 if ~x & 1 else -1)
 
    print(ans)
 
 
t = int(input())
 
for _ in range(t):
    solve()

Two Knights

먼저 어떤 $k$ 에 대해 경우를 모두 세는 방법을 알아봅시다.

두 나이트 중 하나를 $(i, j)$ 에 놓았다고 합시다. 그렇다면 나머지 $k^2 - 1$ 개의 칸 중 먼저 배치한 나이트가 공격하는 위치 최대 $8$ 개를 제외하고 모두 둘 수 있습니다.

이 값을 모두 더한 다음 순서를 고려하지 않기 위해 $2$ 로 나눠 주면 답을 구할 수 있습니다.

예를 들어 $k = 3$ 의 경우 각 좌표마다 해당 나이트가 공격하는 위치의 개수를 적으면 다음과 같습니다.

\begin{array}{|c|c|c|} \hline 2 & 2 & 2 \\ \hline 2 & 0 & 2 \\ \hline 2 & 2 & 2 \\ \hline \end{array}

$(i, j)$ 에 적혀있는 값을 $A_{ij}$ 라 하면 경우의 수는 $\dfrac{\sum ((3^2 - 1) - A_{ij})}{2}$ 가 됩니다.

그러나 $A_{ij}$ 를 하나하나 구하면 시간 복잡도가 $O(k^2)$ 이므로 더 빠른 방법을 사용해야 합니다.

합 부분을 나눠서 쓰면 $\dfrac{(3^2 - 1)3^2 - \sum A_{ij}}{2}$ 입니다.

$(k^2 - 1)k^2$ 을 계산하는 것은 쉬우므로 $\sum A_{ij}$ 만 빠르게 구하면 됩니다.

$k = 5$ 인 경우의 $A_{ij}$ 를 그려봅시다.

\begin{array}{|c|c|c|c|c|} \hline 2 & 3 & 4 & 3 & 2 \\ \hline 3 & 4 & 6 & 4 & 3 \\ \hline 4 & 6 & 8 & 6 & 4 \\ \hline 3 & 4 & 6 & 4 & 3 \\ \hline 2 & 3 & 4 & 3 & 2 \\ \hline \end{array}

$2$ , $3$ , $4$ , $6$ , $8$ 의 개수를 계산하는 식을 찾아봅시다. $5$ , $7$ 은 나이트 행마법 특성상 존재할 수 없는 수입니다.

먼저 $4$ 개의 꼭짓점은 항상 $2$ 입니다. 그리고 해당 꼭짓점과 인접한 총 $8$ 개의 칸은 항상 $3$ 입니다.

이를 제외하고 가장자리에 붙어 있는 칸은 항상 $4$ 입니다. 원래 나이트가 공격하는 $8$ 개의 칸 중 절반은 항상 체스판 밖에 있기 때문입니다.

이와 비슷하게 가장자리에서 한 칸 떨어져 있는 칸은 $6$ , 두 칸 떨어져 있는 칸은 $8$ 입니다.

다만 한 칸 떨어져 있는 칸이라고 하더라도 $2$ 와 대각선으로 인접한 경우에는 예외적으로 $4$ 입니다.

$2$ 는 $4$ 개
$3$ 은 $8$ 개
$4$ 는 $2$ , $3$ 을 제외하고 가장자리인 $4k - 16$ 개에 $2$ 와 인접한 모서리 $4$ 개로 총 $4k - 12$ 개
$6$ 은 한 칸 떨어져 있는 $4(k - 2) - 4$ 개 중 $4$ 가 차지한 $4$ 개를 제외하고 $4k - 16$ 개
$8$ 은 $k^2$ 에서 이를 모두 뺀 $k^2 - (4k - 16) - (4k - 12) - 8 - 4 = k^2 - 8k + 16 = (k - 4)^2$

이 공식은 $k \geq 5$ 에 대해 도출한 식이지만 이보다 작은 $k$ 에 대해서도 직접 계산해 보면 성립하므로 굳이 예외 처리하지 않아도 됩니다.

도출한 식을 이용해서 $\sum A_{ij}$ 를 $O(1)$ 에 계산하고 $(k^2 - 1)k^2$ 에서 빼 주면 체스판의 크기가 $k \times k$ 일 때의 답을 $O(1)$ 에 구할 수 있습니다.

따라서 시간 복잡도 $O(n)$ 에 문제를 해결할 수 있습니다.

코드 (Python)

n = int(input())
 
 
def getCount(k):
    ret = (k * k - 1) * k * k
 
    ret -= 2 * 4
    ret -= 3 * 8
    ret -= 4 * (4 * k - 12)
    ret -= 6 * (4 * k - 16)
    ret -= 8 * (k - 4) ** 2
 
    return ret // 2
 
 
for k in range(1, n + 1):
    print(getCount(k))

Two Sets

두 집합을 편의상 $A$ , $B$ 라고 부르겠습니다.

두 집합에 ㄹ을 옆으로 눕힌 모양 순서대로 자연수를 추가하면 두 합이 동일하게 유지됩니다.

\begin{gathered} A = \{1, 4, 5, 8, \dots\} \\ B = \{2, 3, 6, 7, \dots\} \end{gathered}

$A$ 에 $1$ 을 넣고, $B$ 에 $2$ , $3$ 을 넣고, $A$ 에 $4$ 를 넣고, 이를 계속 반복하는 것입니다.

다만 이러한 방법은 $n$ 이 $4$ 의 배수일 때만 이용할 수 있는 방법입니다.

$1$ 부터 $n$ 까지의 합은 $\dfrac{n(n + 1)}{2}$ 입니다. 따라서 $n$ 또는 $n + 1$ 이 $4$ 의 배수가 아닌 짝수라면 그 합이 홀수가 되어 해가 존재하지 않습니다.

따라서 해가 존재하는 $n$ 은 자기자신이 $4$ 의 배수거나, $n + 1$ 이 $4$ 의 배수여야 합니다.

전자인 경우 앞서 설명한 방법으로 해를 구성할 수 있고, 후자의 경우 $1 + 2 = 3$ 을 이용해서 먼저 $3$ 개를 미리 배치한 후 같은 방법으로 해결할 수 있습니다.

코드 (Python)

def main():
    n = int(input())
 
    if n == 1 or (((n + 1) & ~1) % 4 == 2):
        print("NO")
        return
    print("YES")
 
    A = []
    B = []
    start = 5 - n % 2
 
    if n % 2 == 1:
        A = [1, 2]
        B = [3]
    else:
        A = [1, 4]
        B = [2, 3]
 
    for i in range(start, n, 4):
        A.extend([i, i + 3])
        B.extend([i + 1, i + 2])
 
    print(len(A))
    print(*A)
    print(len(B))
    print(*B)
 
 
main()

Bit Strings

길이가 $n$ 인 비트 문자열은 각 문자가 0 또는 1의 두 가지 경우가 있으므로 총 $2^n$ 개가 존재합니다.

$2^n \bmod (10^9 + 7)$ 을 출력하면 됩니다.

$2^n$ 을 바로 계산하기에는 너무 수가 커지므로 $2$ 를 곱하면서 $10^9 + 7$ 을 넘어갈 때마다 다시 나머지를 취해 주면 됩니다.

이렇게 해도 되는 이유는 곱할 때마다 나머지를 취하는 것과 전부 곱하고 나서 나머지를 취하는 것의 결과가 같기 때문입니다.

증명

곱하려고 하는 $n$ 개의 수를 각각 $a_1, a_2, a_3, \dots, a_n$ 이라 하고, 이를 모두 곱한 다음 $m$ 으로 나눈 나머지를 구해 봅시다.

$a_i$ 를 $m$ 으로 나눈 몫을 $b_i$ , 나머지를 $r_i$ 라 하면 $a_i = mb_i + r_i$ 로 쓸 수 있습니다.

$\prod a_i = \prod (mb_i + r_i)$ 를 전개했을 때 $m$ 을 인수로 갖는 항은 $m$ 으로 나눈 나머지를 취하면 $0$ 이 될 것이므로 결국에는 $\prod r_i$ 만이 남습니다.

따라서 곱할 때마다 나머지를 취하는 것과 전부 곱하고 나머지를 취하는 것은 항상 같습니다.

코드 (Python)

n = int(input())
 
MOD = int(1e9) + 7
 
ans = 1
for _ in range(n):
    ans *= 2
    ans %= MOD
 
print(ans)

Trailing Zeros

정수를 십진법으로 썼을 때 후행 0의 개수는 그 정수가 $10$ 으로 최대 몇 번 나누어 떨어지는지와 같습니다.

계승을 소인수분해했을 때에는 항상 $2$ 의 지수가 $5$ 의 지수보다 크므로, 후행 $0$ 의 개수는 $5$ 의 지수와 같습니다.

$1$ 부터 $n$ 까지 $5$ 의 지수를 하나씩 세면 시간 복잡도가 $O(n\sqrt n)$ 입니다.

대신 $5$ 의 배수, $5^2$ 의 배수, $5^3$ 의 배수의 개수를 전부 세서 더해 주면 $O(\log_5 n)$ 에 답을 구할 수 있습니다.

코드 (Python)

n = int(input())
 
ans = 0
 
i = 5
while i <= n:
    ans += n // i
    i *= 5
 
print(ans)

Coin Piles

일반성을 잃지 않고 $a \leq b$ 라 합시다.

두 가지 제거 방법 중 어느 것을 먼저 쓰는지는 상관이 없습니다.

두 방법을 한 번씩 쓰면 양쪽에서 $3$ 개씩 가져가는 것과 같습니다.

따라서 양쪽에서 $3$ 개씩 가져가는 것을 $c$ 번, 더 많은 쪽 더미에서 $2$ 개 가져가는 방법을 $d$ 번 사용하는 것으로 생각해 봅시다.

양쪽에서 $3$ 개씩 가져가는 것으로 모두 가져가려면 그 전에 양쪽 더미의 동전 개수가 서로 같고 $3$ 의 배수여야 합니다.

따라서 $d$ 번 가져갔을 때 양쪽의 동전 수가 같아야 합니다.

$a - d = b - 2d$ 를 만족하려면 $d = b - a$ 여야 합니다. 이후 남은 동전이 각각 $3$ 의 배수라면 모두 가져갈 수 있고, 그렇지 않다면 불가능합니다.

코드 (Python)

def solve():
    a, b = map(int, input().split())
 
    if a > b:
        a, b = b, a
 
    ans = b - a
    a -= ans
    b -= ans * 2
 
    if a >= 0 and a % 3 == 0 and b % 3 == 0:
        print("YES")
    else:
        print("NO")
 
 
t = int(input())
 
for _ in range(t):
    solve()

Palindrome Reorder

팰린드롬을 구성하기 위해서는 $n$ 이 짝수인 경우 개수가 홀수인 문자가 있으면 안 되고, $n$ 이 홀수인 경우 개수가 홀수인 문자가 $2$ 개 이상 있으면 안 됩니다.

조건을 만족한다면 각 문자의 개수를 세어서 절반을 아무렇게나 만들고 반전시켜 이어붙이면 됩니다.

만약 홀수 개인 문자가 있다면 해당 문자를 그 사이에 넣으면 됩니다.

코드 (Python)

저는 문자의 개수를 셀 때 맵(dictionary)을 사용했지만 배열이나 Counter를 사용해도 괜찮습니다.

s = input()
 
cnt = {}
for c in s:
    if c not in cnt:
        cnt[c] = 0
    cnt[c] += 1
 
half = []
center = ""
odd_cnt = 0
for c in cnt:
    if cnt[c] % 2 == 1:
        center = c
        odd_cnt += 1
 
    half.append(c * (cnt[c] // 2))
 
if len(s) % 2 - odd_cnt < 0:
    print("NO SOLUTION")
else:
    half = "".join(half)
    print(half, center, half[::-1], sep="")

Gray Code

$n = k$ 일 때의 답을 $a_1, a_2, \dots, a_{2^k}$ 라 합시다.

$n = k + 1$ 일 때는 $a_i$ 를 한 번 나열한 후, 각각에 $2^k$ 를 더해 뒤집어서 또 나열해 주면 됩니다.

그러니까 $a_1, a_2, \dots , a_{2^k}, a_{2^k} + 2^k, \dots, a_2 + 2^k, a_1 + 2^k$ 로 만들 수 있습니다.

코드 (Python)

n = int(input())
 
ans = [0, 1]
 
for i in range(1, n):
    for a in reversed(ans):
        ans.append(a + 2**i)
 
for a in ans:
    print(f"{a:0{n}b}")

Tower of Hanoi

$n$ 개의 원판을 모두 오른쪽 기둥으로 옮기려면 가장 큰 원판이 어떤 방법으로든 오른쪽 기둥으로 이동해야 합니다.

그러기 위해서는 나머지 $n - 1$ 개의 원판이 왼쪽이나 오른쪽 기둥에 있으면 안 됩니다.

따라서 아래 방법이 유일한 해법입니다.

왼쪽 기둥에서 $n - 1$ 개의 원판을 가운데 기둥으로 옮기고
가장 큰 원판을 왼쪽에서 오른쪽 기둥으로 옮기고
가운데 $n - 1$ 개의 원판을 오른쪽으로 옮기기

즉, 원판 $n$ 개를 옮기는 것을 원판 $n - 1$ 개를 옮기는 것 두 번으로 해결할 수 있습니다.

따라서 위 해법을 재귀함수로 구현하면 답을 구할 수 있습니다.

원판 $n$ 개를 옮기는 함수의 시간 복잡도를 $O(T(n))$ 이라 하면 $T(n) = 2T(n - 1) + 1$ 이므로 총 시간 복잡도는 $O(2^n)$ 입니다.

코드 (Python)

build_moves(n, s, t)는 s에서 t로 n개의 원판을 옮기는 방법을 구하는 함수입니다.

이때 기둥은 각각 $1$ , $2$ , $3$ 번이고 이를 모두 합한 다음 s와 t를 빼면 나머지 기둥 m의 번호를 알 수 있습니다.

moves = []
 
 
def build_moves(n, s, t):
    if n == 1:
        moves.append((s, t))
        return
 
    m = 6 - s - t
    build_moves(n - 1, s, m)
    moves.append((s, t))
    build_moves(n - 1, m, t)
 
 
n = int(input())
build_moves(n, 1, 3)
 
print(len(moves))
for move in moves:
    print(*move)

Creating Strings

어떤 방법으로든 순열을 모두 구한 다음 중복을 제거하고 정렬해서 출력하면 됩니다.

파이썬에서 제공하는 itertools를 이용하면 쉽게 해결할 수 있습니다.

itertools 코드 (Python)

from itertools import permutations
 
s = input()
 
perms = sorted(set(permutations(s)))
 
print(len(perms))
for perm in perms:
    print(*perm, sep="")

직접 구현해 보는 것도 실력에 도움이 됩니다. 아래는 백트래킹으로 직접 순열을 구하는 코드입니다.

백트래킹 코드 (Python)

s = input()
n = len(s)
 
strings = set()
 
 
def visit_permutations(p, chosen):
    if len(p) == n:
        strings.add("".join(p))
        return
 
    for i in range(n):
        if chosen[i]:
            continue
 
        p.append(s[i])
        chosen[i] = True
 
        visit_permutations(p, chosen)
 
        p.pop()
        chosen[i] = False
 
 
visit_permutations([], [False] * n)
 
print(len(strings))
print(*sorted(strings), sep="\n")

Apple Division

집합을 둘로 나눈다면 한쪽의 합이 정해졌을 때 나머지 부분의 합도 자동으로 정해집니다.

$2^n$ 개의 부분집합에 대해 차를 모두 구해서 가장 작은 것을 출력하면 됩니다.

코드 (Python)

모든 부분 집합을 순회하는 쉬운 방법 중 하나는 비트마스킹을 이용하는 것입니다.

$2^i$ 자리의 비트가 $0$ 이면 미포함, $1$ 이면 포함으로 생각하는 방법입니다.

전체 집합의 크기가 $n$ 이므로 $n$ 개의 비트만 있으면 모든 부분집합을 표현할 수 있습니다.

따라서 $0$ 부터 $2^n - 1$ 까지만 확인하면 됩니다.

총 시간 복잡도는 $O(n2^n)$ 이며, 다른 방법으로 최적화해서 $O(2^n)$ 으로 줄일 수 있으나 $O(n2^n)$ 으로도 제한을 통과하기에는 충분합니다.

n = int(input())
p = list(map(int, input().split()))
 
total = sum(p)
 
ans = total
 
for mask in range(1 << n):
    s = 0
 
    for i in range(n):
        if mask & (1 << i):
            s += p[i]
 
    ans = min(ans, abs(total - 2 * s))
 
print(ans)

Chessboard and Queens

유명한 여덟 퀸 문제입니다.

각 퀸은 같은 행을 공격하므로 퀸은 한 행에 하나만 놓을 수 있습니다.

이 조건을 이용한다면 탐색해야 할 경우의 수는 $8!$ 이 됩니다.

이후 백트래킹으로 퀸을 공격받지 않는 위치에 놓으면서 경우의 수를 모두 세 주면 됩니다.

코드 (Python)

체스보드의 한 변의 길이 $n$ 이 충분히 작으므로 퀸이 공격받는 위치인지 판별할 때 비효율적으로 작성해도 괜찮습니다.

아래 코드의 시간 복잡도는 $O(n \times n!)$ 이고, $O(n!)$ 로 줄일 수 있으나 $O(n \times n!)$ 으로도 제한을 통과하기에는 충분합니다.

n = 8
 
board = [input() for _ in range(n)]
 
placed = [[False] * n for _ in range(n)]
 
 
def in_board(r, c):
    return 0 <= r < 8 and 0 <= c < 8
 
 
def is_attacked(r, c):
    for j in range(n):
        if placed[r][j]:
            return True
 
    for i in range(n):
        if placed[i][c]:
            return True
 
    for k in range(n):
        if in_board(r + k, c + k) and placed[r + k][c + k]:
            return True
        if in_board(r + k, c - k) and placed[r + k][c - k]:
            return True
        if in_board(r - k, c + k) and placed[r - k][c + k]:
            return True
        if in_board(r - k, c - k) and placed[r - k][c - k]:
            return True
 
    return False
 
 
def get_count(row):
    if row == n:
        return 1
 
    ret = 0
 
    for col in range(n):
        if board[row][col] == "*" or is_attacked(row, col):
            continue
 
        placed[row][col] = True
        ret += get_count(row + 1)
        placed[row][col] = False
 
    return ret
 
 
print(get_count(0))

Raab Game I

무승부를 하려면 두 사람이 같은 카드를 내야 합니다.

어떤 카드가 더 큰지가 중요하지 값이 무엇인지는 중요하지 않으므로, 무승부 횟수 $d > 0$ 인 경우 가장 큰 $d$ 개의 카드를 서로 냈다고 생각하고 $n$ 에서 $d$ 를 빼고 다시 문제를 풀면 됩니다.

따라서 $d = 0$ 이라 가정하겠습니다.

먼저 $a$ 와 $b$ 중 하나만 $0$ 인 경우, 즉 한쪽이 모두 승리하는 경우는 불가능합니다.

왜냐하면 $n$ 개의 카드에 대해 각각 더 작은 카드를 상대방이 내야 하는데, 가장 큰 카드 $n$ 은 어떤 카드와 비교해도 작을 수 없기 때문입니다.

이외의 경우에는 답을 항상 구성할 수 있습니다.

$a$ 번 승리한 사람을 $A$ , $b$ 번 승리한 사람을 $B$ 라 합시다.

간단한 방법 중 하나는 $A$ 는 $1$ 부터 $n$ 까지를 순서대로 내고, $B$ 는 이 수열을 왼쪽으로 $a$ 번 회전해서 내는 것입니다.

여기서 말하는 왼쪽으로 회전이란 맨 왼쪽 원소를 가장 오른쪽으로 옮기는 것으로, $1, 2, 3, 4$ 를 한 번 회전하면 $2, 3, 4, 1$ 이 됩니다.

예를 들어 $n = 5$ 이고 $a = 2$ 라면 $B$ 는 $1, 2, 3, 4, 5$ 를 각각 왼쪽으로 $2$ 번 회전한 $3, 4, 5, 1, 2$ 를 순서대로 내면 됩니다.

그렇다면 항상 회전한 횟수만큼 가장 작은 원소들이 오른쪽 끝으로 이동하므로 $B$ 는 회전한 횟수만큼 지고, 나머지만큼 이기게 됩니다.

코드 (Python)

def solve():
    n, a, b = map(int, input().split())
    d = n - a - b
 
    if d < 0 or ((a == 0) ^ (b == 0)):
        print("NO")
        return
 
    print("YES")
 
    l1 = [i for i in range(n, n - d, -1)]
    l2 = list(l1)
 
    n -= d
    for i in range(1, n + 1):
        l1.append(i)
        l2.append((i + a - 1) % n + 1)
 
    print(*l1)
    print(*l2)
 
 
t = int(input())
 
for _ in range(t):
    solve()

Mex Grid Construction

$\operatorname{mex}$ 는 minimum excluded value의 줄임말로, 존재하지 않는 최소 원소를 뜻합니다.

어떤 칸을 기준으로 왼쪽 혹은 위쪽에 위치한 칸은 최대 $2n - 1$ 개입니다.

따라서 $\operatorname{mex}$ 는 항상 $2n$ 이하의 값을 가지므로 시간 복잡도 $O(n)$ 에 $\operatorname{mex}$ 를 계산할 수 있습니다.

총 시간 복잡도는 $O(n^3)$ 입니다.

코드 (Python)

n = int(input())
 
grid = [[0] * n for _ in range(n)]
 
for i in range(n):
    for j in range(n):
        exists = [False] * (2 * n + 1)
 
        for r in range(i):
            exists[grid[r][j]] = True
        for c in range(j):
            exists[grid[i][c]] = True
 
        mex = 0
        while exists[mex]:
            mex += 1
 
        grid[i][j] = mex
 
for row in grid:
    print(*row)

Knight Moves Grid

BFS를 사용해서 해결할 수 있습니다.

$r$ 행 $c$ 열의 좌표를 $(r, c)$ 로 나타냅시다.

처음에 $(0, 0)$ 을 제외한 모든 칸에 원점과의 거리를 $\infty$ 로 설정해두고, Queue를 하나 만들어 $(0, 0)$ 을 넣습니다.

그리고 큐가 빌 때까지 다음을 반복합니다.

큐에서 좌표 $(r, c)$ 를 하나 꺼냅니다.
해당 좌표에서 갈 수 있는 칸 중 거리가 $\infty$ 로 설정되어 있는 모든 칸 $(nr, nc)$ 를 찾습니다.
각 칸의 거리를 $[(r, c)$ 까지의 거리 $]$ $+ 1$ 로 설정하고, $(nr, nc)$ 를 모두 큐에 넣습니다.

코드 (Python)

파이썬의 list는 pop(0)의 시간 복잡도가 $O(n)$ 이므로 대신 $O(1)$ 에 popleft를 지원하는 deque를 사용하면 됩니다.

정수에는 무한대가 없으므로 대신 $-1$ 을 넣어두고 따로 처리했습니다.

from collections import deque
 
dr = [2, 1, -1, -2, -2, -1, 1, 2]
dc = [1, 2, 2, 1, -1, -2, -2, -1]
 
n = int(input())
 
min_cnt = [[-1] * n for _ in range(n)]
 
queue = deque([(0, 0)])
min_cnt[0][0] = 0
 
while queue:
    r, c = queue.popleft()
 
    for k in range(8):
        nr = r + dr[k]
        nc = c + dc[k]
 
        if not (0 <= nr < n and 0 <= nc < n) or min_cnt[nr][nc] != -1:
            continue
 
        min_cnt[nr][nc] = min_cnt[r][c] + 1
        queue.append((nr, nc))
 
for row in min_cnt:
    print(*row)

Grid Coloring I

공식 풀이와 제 풀이 총 두 가지 풀이를 소개하겠습니다.

풀이 I

맨 왼쪽 위부터 답을 구성해 봅시다.

각 칸을 결정할 때에는 왼쪽, 위쪽 칸과는 달라야 하며, 원래 알파벳과도 달라야 합니다.

알파벳의 개수는 총 $4$ 개이므로 위 세 가지를 제외한 알파벳이 항상 하나 이상 존재합니다.

따라서 항상 해를 구성할 수 있고 그 중 아무거나 고르면 됩니다.

코드 (Python)

n, m = map(int, input().split())
 
old_grid = [input() for _ in range(n)]
ans = [[""] * m for _ in range(n)]
 
for i in range(n):
    for j in range(m):
        chars = set("ABCD")
 
        if i > 0 and ans[i - 1][j] in chars:
            chars.remove(ans[i - 1][j])
        if j > 0 and ans[i][j - 1] in chars:
            chars.remove(ans[i][j - 1])
        if old_grid[i][j] in chars:
            chars.remove(old_grid[i][j])
 
        ans[i][j] = chars.pop()
 
for row in ans:
    print("".join(row))

풀이 II

원래 글자와 달라야 한다는 조건이 없었다면 체스판처럼 번갈아가면서 ABABABA처럼 채우는 방법이 가능했을 것입니다.

그러나 알파벳이 총 $4$ 개나 주어지므로 AB로 이루어진 체스판과 CD로 이루어진 체스판을 적절히 섞어서 해를 구성할 수 있습니다.

원래 문자가 A 혹은 B인 칸에서는 CD 체스판을, C 혹은 D인 칸에서는 AB 체스판을 사용합니다.

이렇게 하면 원래 문자와 항상 다르고, 체스판 특성에 의해 인접한 문자와도 항상 다르게 되어 해를 구성할 수 있습니다.

코드 (Python)

n, m = map(int, input().split())
 
grid = [list(map(lambda c: ord(c) - ord("A"), input())) for _ in range(n)]
 
for i in range(n):
    for j in range(m):
        grid[i][j] = 2 * (grid[i][j] <= 1) + (i + j) % 2
 
for row in grid:
    print(*map(lambda x: chr(ord("A") + x), row), sep="")

Digit Queries

$10^9$ 까지의 수를 모두 나열해도 숫자의 개수는 대략 $10^{10}$ 으로, $k$ 의 최댓값보다 훨씬 작아 수를 하나씩 나열하면서 계산하는 방법은 너무 느립니다.

먼저 $n$ 자리 수를 모두 나열하면 길이가 얼마인지 살펴봅시다.

$n$ 자리 숫자의 개수는 $10^{n - 1}$ 부터 $10^n - 1$ 까지 $9 \times 10^{n - 1}$ 개이고, 각 수가 $n$ 자리이므로 총 $9n \times 10^{n - 1}$ 개의 숫자를 차지합니다.

이를 이용하면 $k$ 번째 숫자가 적어도 몇 자리 수에 위치하는지 알아낼 수 있습니다.

$n$ 자리 수를 모두 나열했을 때 길이가 $L_n$ 이라 하면 $k \leq \sum\limits_{i = 1}^d L_i$ 를 만족하는 가장 작은 $d$ 를 찾으면 됩니다.

$k' = k - \sum\limits_{i = 1}^{d - 1} L_i$ 라 합시다. $d$ 자리 수를 나열한 다음 $k'$ 번째 숫자를 찾으면 답을 구할 수 있습니다.

$d$ 자리 수는 길이가 $d$ 이므로 $1 \leq k' \leq d$ 를 만족할 때 까지 $k'$ 에서 $d$ 를 뺀 다음, $(10^{d - 1} +\$ 뺀 횟수 $)$ 의 $k'$ 번째 숫자를 찾으면 됩니다.

이는 나눗셈으로 빠르게 찾을 수 있습니다. $10^{d - 1} + \left\lfloor \dfrac{k' - 1}{d} \right\rfloor$ 의 $((k' - 1) \bmod d) + 1$ 번째 숫자를 찾으면 됩니다.

코드 (Python)

for _ in range(int(input())):
    k = int(input())
 
    d = 1
    while k - d * 9 * 10 ** (d - 1) > 0:
        k -= d * 9 * 10 ** (d - 1)
        d += 1
 
    num = 10 ** (d - 1) + (k - 1) // d
    k = (k - 1) % d
    print(str(num)[k])

String Reorder

문자열에서 등장한 횟수가 가장 많은 문자가 등장한 횟수를 $c$ 라 합시다.

해당 문자는 인접할 수 없으므로 아무리 가까워도 한 칸은 떨어져 있어야 합니다.

미리 해당 문자를 한 칸씩 띄어서 배치해 봅시다. 그렇다면 문자 사이의 빈칸은 $c - 1$ 개가 생깁니다.

이 빈칸을 전부 채우는 경우 문자열의 길이는 $2c - 1$ 이 되고, 따라서 문자열의 길이 $n$ 이 이보다 작으면 안 됩니다.

해당 조건을 만족하지 않으면 해를 구성할 수 없습니다.

해당 조건을 만족시키는 경우 알파벳을 하나 배치하고 나서도 남은 문자들이 위 조건을 만족하도록 아무 알파벳이나 배치하면 됩니다.

그러한 알파벳은 항상 존재합니다.

증명

만약 남아 있는 문자들 중 a의 개수 $c$ 가 $2c - 1 = m$ 을 만족해서 다음에 a를 배치해야만 하고, 이전에 a를 배치했기 때문에 불가능한 경우를 생각해 봅시다.

그렇다면 마지막으로 a를 배치하기 전에 a의 개수는 $c + 1$ 이고 $2c + 1 > m + 1$ 을 만족했을 것입니다. 이는 재배치가 불가능한 조건이므로 a를 배치했었다는 것 자체가 모순입니다.

따라서 a가 아닌 다른 문자를 배치했던 경우만 존재하고, 항상 a를 배치할 수 있게 됩니다.

가능한 알파벳 중 사전순으로 가장 빠른 것을 배치하면 됩니다.

따라서 총 $n$ 번 $O(26)$ 개의 문자에 대해 지금 배치해도 되는지 $O(26)$ 에 검사하면 총 시간 복잡도 $O(26^2n)$ 에 문제를 해결할 수 있습니다.

시간 제한이 조금 엄격하지만 가벼운 연산만으로 알고리즘을 작성할 수 있으므로 정답을 받을 수 있습니다.

개수의 최댓값을 업데이트마다 $O(1)$ 에 관리하는 방법으로 시간 복잡도를 상수가 작은 $O(n)$ 으로도 줄일 수 있지만 여기서는 생략하겠습니다.

코드 (Python)

def main():
    s = input()
    n = len(s)
    chars = sorted(set(s))
    cnt = [0] * 26  # dictionary를 쓰면 시간 초과가 나니 주의
 
    def can_construct(length):
        for c in chars:
            c_idx = ord(c) - ord("A")
 
            if cnt[c_idx] > (length + 1) // 2:  # 2c - 1 > n과 동치
                return False
        return True
 
    for c in s:
        cnt[ord(c) - ord("A")] += 1
 
    if not can_construct(n):
        print(-1)
        return
 
    last = "#"
    for i in range(1, n + 1):
        for c in chars:
            c_idx = ord(c) - ord("A")
 
            if c == last or cnt[c_idx] == 0:
                continue
 
            cnt[c_idx] -= 1
            if can_construct(n - i):
                print(c, end="")
                last = c
                break
            cnt[c_idx] += 1
 
 
main()

Grid Path Description

전형적인 백트래킹 + 가지치기류 문제입니다.

다만 파이썬에서 이걸 해결하려면 가지치기뿐 아니라 다양한 최적화를 도입해야 합니다.

제가 사용한 가지치기와 최적화를 소개하겠습니다.

가지치기 1

만약 $49$ 개의 칸을 전부 방문하지 않았는데 목적지에 도착했다면 문제의 조건을 만족시킬 수 없으므로 가지치기합니다.

가지치기 2

도착지를 제외하고 아직 미방문인 인접 칸 $C$ 에 대해 $C$ 와 인접한 미방문 칸이 한 개라면 지금 당장 방문해야 합니다.

그러한 칸이 여러 개라면 현재까지의 경로는 문제의 조건을 만족시킬 수 없으므로 가지치기합니다.

가지치기 3

현재 칸에서 왼쪽과 오른쪽만 갈 수 있거나, 위쪽과 아래쪽만 갈 수 있는 경우 격자가 절반으로 갈라져 한 쪽으로 가면 다른 쪽으로 갈 수 없게 됩니다.

따라서 문제의 조건을 만족시킬 수 없으므로 가지치기합니다.

최적화 1

모든 좌표를 하나의 정수로 나타냅니다.

$r$ 행 $c$ 열의 좌표 $(r, c)$ 는 $nr + c$ 로 일대일 대응시킬 수 있습니다.

최적화 2

방문 여부를 비트마스킹으로 관리합니다.

좌표 $p = nr + c$ 의 방문 여부를 비트마스크의 $p$ 번째 비트로 관리합니다.

최적화 3

각 칸마다 인접한 칸들의 좌표를 미리 전처리합니다.

매번 인접한 칸을 계산하지 않고, 각 칸마다 인접한 칸의 좌표를 담아두고 해당 배열을 순회함으로써 조건 분기(if문)를 줄입니다.

최적화 4

인접한 칸 중 방문하지 않은 것의 개수를 빠르게 계산할 수 있도록 인접한 칸의 좌표들로만 만든 비트마스크를 전처리합니다.

예를 들어 인접한 칸의 좌표가 $a$ , $b$ 라면 $2^a + 2^b$ 를 미리 계산해 둡니다.

이후 방문 비트마스크의 complement와 and 연산을 하고 켜져있는 비트의 개수를 세면 미방문 이웃의 개수를 빠르게 셀 수 있습니다.

더 자세한 내용은 코드를 참고해 주세요.

코드 (Python)

def main():
    n = 7
    dr = [0, -1, 0, 1]
    dc = [1, 0, -1, 0]
    destination = n * (n - 1)
 
    DIRECTIONS = list(range(4))
    R, U, L, D = DIRECTIONS
 
    RL = 1 << R | 1 << L
    UD = 1 << U | 1 << D
 
    neighbor_pos: list[list[tuple[int, int]]] = [[] for _ in range(n * n)]
    neighbor_masks: list[int] = [0] * (n * n)
    for r in range(n):
        for c in range(n):
            pos = n * r + c
 
            for d in DIRECTIONS:
                nr = r + dr[d]
                nc = c + dc[d]
 
                if not (0 <= nr < n and 0 <= nc < n):
                    continue
 
                npos = n * nr + nc
 
                neighbor_pos[pos].append((npos, d))
                neighbor_masks[pos] |= 1 << npos
 
    def dirToIdx(dir):
        if dir == "R":
            return R
        if dir == "U":
            return U
        if dir == "L":
            return L
        if dir == "D":
            return D
        return -1
 
    s = list(map(dirToIdx, input()))
 
    def search(pos: int, depth: int, visit_mask: int):
        if depth == len(s):
            return 1 if pos == destination else 0
        if pos == destination:
            return 0
 
        idx = depth
        possible_directions = 0
        possible_positions: list[tuple[int, int]] = []
        must_visit: tuple[int, int] | None = None
 
        for npos, d in neighbor_pos[pos]:
            if visit_mask & (1 << npos):
                continue
 
            possible_directions |= 1 << d
            possible_positions.append((npos, d))
 
            if npos == destination:
                continue
 
            unvisited_neighbor_cnt = (neighbor_masks[npos] & ~visit_mask).bit_count()
 
            if unvisited_neighbor_cnt == 1:
                if s[idx] != -1 and s[idx] != d:
                    return 0
 
                if must_visit is not None:
                    return 0
 
                must_visit = (npos, d)
 
        if possible_directions == RL or possible_directions == UD:
            return 0
        if must_visit is not None:
            possible_positions = [must_visit]
 
        ret = 0
        for npos, d in possible_positions:
            if s[idx] != -1 and d != s[idx]:
                continue
 
            ret += search(npos, depth + 1, visit_mask | 1 << npos)
 
        return ret
 
    print(search(0, 0, 1))
 
 
main()

Weird Algorithm

Missing Number

Repetitions

Increasing Array

Permutations

Number Spiral

Two Knights

Two Sets

Bit Strings

Trailing Zeros

Coin Piles

Palindrome Reorder

Gray Code

Tower of Hanoi

Creating Strings

Apple Division

Chessboard and Queens

Raab Game I

Mex Grid Construction

Knight Moves Grid

Grid Coloring I

Digit Queries

String Reorder

Grid Path Description

가지치기 1

가지치기 2

가지치기 3

최적화 1

최적화 2

최적화 3

최적화 4

댓글