SSPC 4차

작성일 | In

4차에서는 skysky_noob이 날뛰는 바람에 골드 문제가 3개나 출제되었습니다.
절대로 제 잘못이 아닙니다. 아무튼 그렇습니다.

4차 스코어보드

랭킹 아이디 A B C D E  
1 skysky_noob 2 / 24 1 / 21 1 / 77 0 / -- 0 / -- 3 / 122
2 skuru 2 / 25 1 / 8 0 / -- 5 / -- 0 / -- 2 / 33
3 calmtot 1 / 94 4 / 145 0 / -- 0 / -- 0 / -- 2 / 239
4 cws111204 3 / 45 0 / -- 0 / -- 0 / -- 0 / \ – 1 / 45

전체 순위

순위 아이디 맞힌 문제 / 페널티
1 skuru 17 / 703
2 skysky_noob 15 / 461
3 cws111204 7 / 451
4 skipperkim307 5 / 420

문제 풀이

A. 컵라면 측정하기

브론즈 III 브론즈 III

피타고라스의 정리를 이용하면 높이를 구할 수 있습니다.

Python 코드
1
2
3
4
k = int(input())
d1, d2 = map(int, input().split())

print(k*k - (d1 - d2)**2 / 4)

B. Three Dots

실버 II 실버 II

문제에서 점들이 모두 서로 다르다고 했으므로 집합을 이용해 $O(N^2)$에 해결할 수 있습니다.
두 점을 잡고, 차를 구해 나머지 한 점이 존재하는지 구하면 됩니다.

Python 코드
1
2
3
4
5
6
7
8
9
10
for t in range(int(input())):
    n = int(input())
    points = sorted(map(int, input().split()))
    points_set = set(points)
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            if (points[j] - points[i]) + points[j] in points_set:
                ans += 1
    print(ans)

C. 전화번호 만들기

골드 III 골드 III

그룹을 지을 때, 각각의 그룹에는 반드시 2개나 3개의 숫자가 들어갑니다.
따라서 왼쪽부터 $i$번째 숫자까지 품질의 최대를 $dp[i]$라 하면
$dp[i]$는 $dp[i-2]$와 $dp[i-3]$을 이용해 구할 수 있습니다.

만약 최적의 답이 여러가지라면 사전순으로 가장 앞서는 것을 출력해야하는데,
하이픈이 가장 우선이므로 앞에서부터 최대한 하이픈을 일찍 넣으면 됩니다.

처음 주어진 번호를 뒤집고 나서 끝에서부터 역추적하면 정방향으로 답을 찾는 것과 같습니다.
따라서 번호를 뒤집고 나서, $dp$배열을 채웁니다. 이때 가능하면 그룹의 크기를 2로 하도록 하고 역추적 하면 됩니다.

아래 코드에서 $prev$배열은 $i$번째 숫자를 포함하는 그룹 이전의 그룹 끝 위치입니다.
예를 들어 그룹이 “50-88-638”으로 나눠진다면 $prev[3] = 1$이고, $prev[6] = 3$입니다.
따라서 $i = prev[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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
number = input()[::-1]

dp = [0 for _ in range(len(number))]
prev = [None for _ in range(len(number))]

if number[0] == number[1]:
    dp[1] += 2
if 3 <= len(number):
    numset = set(number[:3])
    if len(numset) == 1:
        dp[2] += 2
    elif len(numset) == 2:
        dp[2] += 1
if 4 <= len(number):
    dp[3] = dp[1]
    if number[2] == number[3]:
        dp[3] += 2
    prev[3] = 1


for i in range(4, len(number)):
    two = dp[i - 2]
    numset = set((number[i], number[i - 1]))
    if len(numset) == 1:
        two += 2

    three = dp[i - 3]
    numset.add(number[i - 2])
    if len(numset) == 1:
        three += 2
    elif len(numset) == 2:
        three += 1

    prev[i] = i - 2 if three <= two else i - 3
    dp[i] = max(two, three)


ans = ""
i = len(number) - 1
while i > 2:
    ans += number[i : prev[i] : -1] + "-"
    i = prev[i]
print(ans + number[i::-1])

D. 만화에서 나오는 거 따라하고 그러면 안 된다

골드 II 골드 II

모든 정점에 대해 토카의 집에서부터 최단거리는 데이크스트라 알고리즘을 이용하면 $O(ElogE)$에 구할 수 있습니다. ($E$는 간선의 개수)

한별 선배의 경로를 찾기 위해서, 먼저 간선들을 간선 개수와 나무 번호로 내림차순 정렬합니다.
그리고 bfs를 통해 한별 선배의 집에서 학교까지 최단거리를 찾고, $prev$배열을 통해 그 경로를 역추적합니다.

한별 선배의 경로 중 토카가 가장 빨리 도착할 수 있는 나무가 답이 됩니다.

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
import sys
from heapq import *
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

n, m = map(int, input().split())
a, b, c = map(int, input().split())

connected_woods = [[] for _ in range(n + 1)]
for _ in range(m):
    i, j, k = map(int, input().split())
    connected_woods[i].append((j, k))
    connected_woods[j].append((i, k))

for i in range(1, n + 1):
    connected_woods[i].sort(key=lambda e: (-len(connected_woods[e[0]]), -e[0]))

# toca
toca_dist = [float("inf") for _ in range(n + 1)]
toca_dist[a] = 0
queue = [(0, a)]
while queue:
    cur_dist, cur = heappop(queue)
    if toca_dist[cur] < cur_dist:
        continue
    for next_, edge_dist in connected_woods[cur]:
        next_dist = cur_dist + edge_dist
        if next_dist < toca_dist[next_]:
            toca_dist[next_] = next_dist
            heappush(queue, (next_dist, next_))

# hanbyeol
visited = [False for _ in range(n + 1)]
visited[b] = True
prev = [None for _ in range(n + 1)]
queue = deque([b])
while queue:
    cur = queue.popleft()

    for next_, _ in connected_woods[cur]:
        if visited[next_]:
            continue
        visited[next_] = True
        prev[next_] = cur
        queue.append(next_)

ans = c
hanbyeol = c
while hanbyeol != b:
    hanbyeol = prev[hanbyeol]
    ans = min(hanbyeol, ans, key=lambda w: (toca_dist[w], w))
print(ans)

처음에 간선을 정렬하지 않고, 학교에서 한별 선배의 집으로 bfs를 통해 각 정점에서 학교까지의 은행나무 개수를 구하고 나서
한별 선배가 등교하는 규칙대로 역추적하는 방법도 있습니다.
걸리는 시간은 비슷한 것 같네요.

E. Overdose Runner

골드 I 골드 I

그냥 구현량이 많을 뿐인 시뮬레이션 문제입니다.
Monster 클래스와 Player 클래스를 만들고 플레이어의 행동을 전부 메소드로 처리했습니다.

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
class Monster:
    def __inif__(self):
        self.health: int
        self.defense: int
        self.exp: int

    def __eq__(self, string: str) -> bool:
        return string == "m"


class Player:
    def __init__(self):
        self.atk = 5
        self.reach = 1
        self.speed = 1
        self.need_exp = 10
        self.exp = 0
        self.level = 1
        self.cleared = False

        self.dose_count = 0
        self.OVERDOSE = 0  # 양수면 OVERDOSE 0이면 해제
        self.active_point = 0

        self.x: int
        self.y: int

    def behave(self, amount: int):
        self.active_point += amount
        self.OVERDOSE = max(self.OVERDOSE - amount, 0)

    # 순간이동

    def move(self, dx: int, dy: int):  # 각각 -1, 0, 1중 하나
        x = self.x + self.speed * dx
        y = self.y + self.speed * dy
        if x < 0 or n <= x or y < 0 or m <= y:
            return
        square = world[x][y]
        if square == "m" or square == "*":
            return
        self.x = x
        self.y = y
        self.behave(1)

    def up(self):
        self.move(-1, 0)

    def down(self):
        self.move(1, 0)

    def left(self):
        self.move(0, -1)

    def right(self):
        self.move(0, 1)

    # 대기

    def wait(self):
        self.behave(1)

    # 경험치 정산

    def levelup(self):
        while self.need_exp <= self.exp:
            self.exp -= self.need_exp

            self.atk += self.level
            self.reach += 1
            self.need_exp += 10
            self.level += 1

    # 공격

    def attack(self, dx: int, dy: int):  # 각각 -1, 0, 1중 하나
        if self.OVERDOSE:
            return
        self.behave(3)
        x, y = self.x, self.y
        for _ in range(self.reach):
            x += dx
            y += dy
            if world[x][y] == "*":
                break
            if world[x][y] != "m":
                continue
            monster: Monster = world[x][y]
            if self.atk < monster.defense:
                continue
            monster.health -= self.atk - monster.defense
            if monster.health <= 0:
                world[x][y] = "."
                self.exp += monster.exp
        self.levelup()

    def attack_up(self):
        self.attack(-1, 0)

    def attack_down(self):
        self.attack(1, 0)

    def attack_left(self):
        self.attack(0, -1)

    def attack_right(self):
        self.attack(0, 1)

    # 약 먹기

    def dose(self, delta: int):
        if self.OVERDOSE:
            return
        self.behave(2)
        self.dose_count += 1
        self.speed += delta
        self.speed = max(self.speed, 0)

        if self.dose_count == 5:
            self.OVERDOSE = 10
            self.dose_count = 0

    def dose_up(self):
        self.dose(1)

    def dose_down(self):
        self.dose(-1)

    # 클리어

    def clear(self):
        if self.OVERDOSE:
            return
        self.cleared = world[self.x][self.y] == "g"


player = Player()

n, m = map(int, input().split())
world = [list(input()) for _ in range(n)]
monsters: list[Monster] = []
for i in range(n):
    for j in range(m):
        if world[i][j] == "m":
            world[i][j] = Monster()
            monsters.append(world[i][j])
        if world[i][j] == "p":
            player.x, player.y = i, j
            world[i][j] = "."

k = int(input())

for i, health in enumerate(map(int, input().split())):
    monsters[i].health = health
for i, defense in enumerate(map(int, input().split())):
    monsters[i].defense = defense
for i, exp in enumerate(map(int, input().split())):
    monsters[i].exp = exp

s = int(input())

for behave in input().split():
    match behave:
        case "u":
            player.up()
        case "d":
            player.down()
        case "l":
            player.left()
        case "r":
            player.right()
        case "w":
            player.wait()
        case "au":
            player.attack_up()
        case "ad":
            player.attack_down()
        case "al":
            player.attack_left()
        case "ar":
            player.attack_right()
        case "du":
            player.dose_up()
        case "dd":
            player.dose_down()
        case "c":
            player.clear()
            if player.cleared:
                break

print(player.level, player.exp)
print(player.active_point)

world[player.x][player.y] = "p"
for i in range(n):
    for j in range(m):
        print("m" if world[i][j] == "m" else world[i][j], end="")
    print()

for monster in monsters:
    if monster.health <= 0:
        continue
    print(monster.health, end=" ")

SSPC 4차