SSPC 3차

작성일 | In

3차는 2차와 다르게 브론즈 문제 1개, 실버 문제 2개, 골드 문제 2개로 구성됩니다.
3차까지의 스코어보드를 확인하고, 문제 풀이를 적어보겠습니다.

3차 스코어보드

랭킹 아이디 A B C D E  
1 skuru 1 / 1 1 / 4 7 / 176 1 / 37 1 / 80 5 / 298
2 skysky_noob 1 / 2 1 / 15 1 / 57 1 / 35 1 / -- 4 / 109
3 calmtot 1 / 9 1 / 43 0 / -- 0 / -- 0 / -- 2 / 52
4 cws111204 3 / 46 1 / 50 1 / -- 0 / -- 0 / -- 2 / 96
5 skipperkim307 1 / 32 0 / -- 0 / -- 0 / -- 0 / -- 1 / 32

calmtot님은 이번에 깜짝 참가하셨습니다.

전체 순위

순위 아이디 맞힌 문제 / 페널티
1 skuru 15 / 670
2 skysky_noob 12 / 339
3 cws111204 6 / 406
4 skipperkim307 5 / 420

문제 풀이

A. 단원평가

브론즈 III 브론즈 III

단순한 구현 문제입니다.

Python 코드
1
2
3
4
5
6
7
8
a, b, c = map(int, input().split())

if a == 0:
    print(c ** 2 - b)
elif b == 0:
    print(c ** 2 - a)
else:
    print(int((a + b)**(1/2)))

B. 그림 비교

브론즈 I 브론즈 I

두 그림을 뽑는 모든 경우에 대해 두 그림의 다른 칸 수를 세주면 됩니다.

Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n = int(input())

paints = [[input() for _ in range(5)] for _ in range(n)]


def getDiff(l1, l2):
    diff = 0
    for i in range(5):
        for j in range(7):
            if l1[i][j] != l2[i][j]:
                diff += 1
    return diff


min_diff = float("inf")
min_diff_num = (0, 1)
for i in range(n):
    for j in range(i + 1, n):
        diff = getDiff(paints[i], paints[j])
        if diff < min_diff:
            min_diff_num = (i + 1, j + 1)
            min_diff = diff

print(*min_diff_num)

C. 문장

실버 III 실버 III

1부터 999까지 모두 구해보면서 문장에 들어갈 수 있는 수를 찾으면 됩니다.

1부터 9까지, 11부터 19까지, 10부터 90까지 미리 구해 놓은 다음
백의 자리를 먼저 처리합니다.
십의 자리 + 일의 자리가 [11, 19]에 속한다면 예외처리 해 줍니다.
그리고 나머지를 처리하면 됩니다.

Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
n = int(input())

one = [
    "",
    "one",
    "two",
    "three",
    "four",
    "five",
    "six",
    "seven",
    "eight",
    "nine",
]
two = [
    "",
    "ten",
    "twenty",
    "thirty",
    "forty",
    "fifty",
    "sixty",
    "seventy",
    "eighty",
    "ninety",
]

exept = {
    11: "eleven",
    12: "twelve",
    13: "thirteen",
    14: "fourteen",
    15: "fifteen",
    16: "sixteen",
    17: "seventeen",
    18: "eighteen",
    19: "nineteen",
}

numStr = ""
words = [input() for _ in range(n)]
wordlen = sum(map(len, words)) - 1

for i in range(1, 1000):
    num = ""
    hundred = i // 100
    if hundred != 0:
        num += one[hundred] + "hundred"

    twodigits = i % 100
    if 10 < i % 100 < 20:
        num += exept[twodigits]
    else:
        num += two[i % 100 // 10] + one[i % 10]

    if wordlen + len(num) == i:
        numStr = num
        break

for w in words:
    print(numStr if w == "$" else w, end=" ")

D. 이진수 변환

골드 V 골드 V

자연수 $x_0$의 비트 중 1의 개수가 $N$미만이면 수열 $X$는 존재하지 않습니다.

수열 $X$가 존재하는 경우에 대해 생각해 봅시다.

$x_n$에서 여러개의 비트를 껐고, 이게 차의 최댓값이라고 칩시다.
이때 $x_n$의 최상위 비트를 무조건 꺼야 합니다. $x_n$의 최상위 비트가 나머지 비트를 모두 합한 것보다 크기 때문입니다.
따라서 $x_n$의 최상위 비트를 단독으로 끄는 것이 $D(X)$의 최댓값을 최소화 하는 방법입니다.

$x_n$에서 여러개의 비트를 껐고, 이게 차의 최솟값이라고 칩시다.
이때 끈 비트들의 최댓값보다 작은 비트는 남지 않아야 합니다. 위와 비슷하게 작은 비트를 끄는 것이 더 작기 때문입니다.
따라서 가능한 최하위 비트들을 연속으로 많이 끄는 것이 $D(X)$의 최솟값을 최대화 하는 방법입니다.

최댓값을 최소화 하는 방법과 최솟값을 최대화 하는 방법이 서로 충돌하지 않으므로 최적해를 보장합니다.

Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from math import log2, floor

x0, n = map(int, input().split())

x = x0
x1Count = 0
while x:
    if x & 1:
        x1Count += 1
    x >>= 1

if x1Count < n:
    print(-1)
    exit()

count = 0
while x0 and count < n - 1:
    digit = len(bin(x0)) - 2
    x0 -= 2 ** (digit - 1)
    print(x0, end=" ")
    count += 1
print(0)

E. 말이 되고픈 원숭이

골드 III 골드 III

조금 복잡한 bfs문제입니다. 나이트의 움직임이 꽤나 복잡하나, dx배열과 dy배열 테크닉을 이용하면
가독성을 살리면서 구현할 수 있습니다.

어떤 칸을 방문 했을 때 남은 나이트 이동 횟수가 많은 것이 유리하므로 남은 나이트 이동 횟수까지 모두 고려해 방문처리를 해주어야 합니다.

구현하기 귀찮아서 모든 나이트 이동 횟수를 따로 방문처리 해 주었습니다.

Python 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
from collections import deque

k = int(input())
w, h = map(int, input().split())

world = [list(map(int, input().split())) for _ in range(h)]

queue = deque([(0, 0, 0)])  # x, y, 말점프횟수

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
ndx = [-1, -2, -2, -1, 1, 2, 2, 1]
ndy = [-2, -1, 1, 2, -2, -1, 1, 2]

visited = [[[float("inf") for _ in range(k + 1)] for _ in range(w)] for _ in range(h)]
visited[0][0][0] = 0

arrived = False

while queue:
    x, y, jump = queue.popleft()

    if (x, y) == (h - 1, w - 1):
        print(visited[x][y][jump])
        arrived = True
        break

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if (
            0 <= nx < h
            and 0 <= ny < w
            and visited[nx][ny][jump] == float("inf")
            and world[nx][ny] != 1
        ):
            queue.append((nx, ny, jump))
            visited[nx][ny][jump] = visited[x][y][jump] + 1

    if jump >= k:
        continue

    for i in range(8):
        nx = x + ndx[i]
        ny = y + ndy[i]

        if (
            0 <= nx < h
            and 0 <= ny < w
            and visited[nx][ny][jump + 1] == float("inf")
            and world[nx][ny] != 1
        ):
            queue.append((nx, ny, jump + 1))
            visited[nx][ny][jump + 1] = visited[x][y][jump] + 1

if not arrived:
    print(-1)

SSPC 3차