랜덤 마라톤 · 코스 72

작성일 | In

랜덤 마라톤 완주

A. 공약수

브론즈 II 브론즈 II

유클리드 호제법으로 공약수를 구한 뒤 약수를 출력하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b

    return a


def main():
    n = int(input())
    g = 0

    for i in map(int, input().split()):
        g = gcd(g, i)

    for d in range(1, g + 1):
        if g % d == 0:
            print(d)


main()

B. 디지털시계

브론즈 I 브론즈 I

문제에서 요구하는 것을 잘 구현하면 됩니다.

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
class Time:
    def __init__(self, time: str):
        self.h, self.m, self.s = map(int, time.split(":"))

    def add(self, sec: int):
        self.s += sec

        if self.s >= 60:
            self.m += self.s // 60
            self.s %= 60

        if self.m >= 60:
            self.h += self.m // 60
            self.m %= 60

        if self.h >= 24:
            self.h %= 24

    def __ne__(self, other: object) -> bool:
        if isinstance(other, Time):
            return self.h != other.h or self.m != other.m or self.s != other.s
        return True

    def __eq__(self, other: object) -> bool:
        return not self != other

    def isMultipleOf(self, num: int) -> bool:
        return (self.h * 10000 + self.m * 100 + self.s) % num == 0


def main():
    for _ in range(3):
        cnt = 0

        start, end = map(Time, input().split())
        end.add(1)

        if start == end:
            if start.isMultipleOf(3):
                cnt += 1
            start.add(1)

        while start != end:
            if start.isMultipleOf(3):
                cnt += 1

            start.add(1)

        print(cnt)


main()

C. 줄자접기

실버 III 실버 III

줄자의 길이를 $l$이라 하고 수직선 위의 두 점 $0$과 $l - 1$을 잇는 선분으로 생각해 봅시다.

점 $m$을 기준으로 반으로 접으면 줄자의 길이는 $\max(m, l - m)$이 됩니다.

접는 점을 원점인 $0$으로 재조정하면 $m$보다 왼쪽에 있는 점 $x$는 $m - x$, 오른쪽에 있는 점 $y$는 $y - m$으로 바꿀 수 있습니다.

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
def main():
    length = float(input())
    red = sorted(map(float, input().split()))
    blue = sorted(map(float, input().split()))
    yellow = sorted(map(float, input().split()))

    m = (red[0] + red[1]) / 2
    length = max(m, length - m)

    blue = sorted(map(lambda x: abs(x - m), blue))
    yellow = sorted(map(lambda x: abs(x - m), yellow))

    if blue[0] != blue[1]:
        m = (blue[0] + blue[1]) / 2

        yellow = sorted(map(lambda x: abs(x - m), yellow))
        length = max(m, length - m)

    if yellow[0] != yellow[1]:
        m = (yellow[0] + yellow[1]) / 2
        length = max(m, length - m)

    print(f"{length:.1f}")


main()

D. 아이템 배치하기

실버 II 실버 II

강화력이 큰 것부터 내림차순으로 배치하는것이 이득입니다.

현재까지 강화된 아이템의 최대 인덱스를 관리하는 방법으로 $\mathcal{O}(N)$에 해결할 수 있습니다.

강화력이 $0$이면 break하도록 하면 현재까지 봤던 아이템들은 모두 강화된 상태이므로 강화된 아이템의 최대 인덱스가 $N$이 넘어가면 $N$개가 모두 강화됨을 알 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def main():
    N = int(input())
    A = sorted(map(int, input().split()), reverse=True)

    r = -1

    for i in range(N):
        if A[i] == 0:
            break

        r = min(max(r, i + A[i] - 1), N - 1)

    print(r + 1)


main()

E. 이미지 축소

실버 I 실버 I

연속으로 열이 같은 모든 경우의 최대 공약수, 행이 같은 모든 경우의 최대 공약수를 각각 구하면 가장 큰 $i, j$를 구할 수 있습니다.

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
def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a


def main():
    ni, mj = map(int, input().split())

    image = [list(input()) for _ in range(ni)]

    j = 0
    consecutive = 1
    for c in range(1, mj):
        isSame = True
        for r in range(ni):
            if image[r][c] != image[r][c - 1]:
                isSame = False

        if isSame:
            consecutive += 1
        else:
            j = gcd(j, consecutive)
            consecutive = 1

    j = gcd(j, consecutive)

    i = 0
    consecutive = 1
    for r in range(1, ni):
        isSame = True
        for c in range(0, mj, j):
            if image[r][c] != image[r - 1][c]:
                isSame = False

        if isSame:
            consecutive += 1
        else:
            i = gcd(i, consecutive)
            consecutive = 1

    i = gcd(i, consecutive)

    print(ni // i, mj // j)
    for r in range(0, ni, i):
        for c in range(0, mj, j):
            print(image[r][c], end="")
        print()


main()

F. 가희와 무궁화호

골드 V 골드 V

그냥 열심히 구현하면 됩니다…

다음 날로 넘어가는 부분을 구현할 때 주의합시다.

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
from typing import cast


class Time:
    def __init__(self, h: int, m: int):
        self.h = h
        self.m = m

    @staticmethod
    def parseTime(time: str) -> "Time":
        if time == "-:-":
            return Time(0, 0)
        return Time(*map(int, time.split(":")))

    def __int__(self) -> int:
        return self.h * 60 + self.m

    def __str__(self) -> str:
        return f"{self.h:0>2}:{self.m:0>2}"

    def __add__(self, other: "int | Time") -> "Time":
        m = int(self) + int(other)

        isNegative = m < 0
        m = abs(m)

        h = m // 60
        m %= 60

        return Time(-h, -m) if isNegative else Time(h, m)

    def __sub__(self, other: "Time") -> "Time":
        return self + (-int(other))

    def getDuration(self, to: "Time") -> "Time":
        t = to - self

        if int(t) < 0:
            t += Time(24, 0)

        return t


dist = {
    "Seoul": 0,
    "Yeongdeungpo": 9.1,
    "Anyang": 23.9,
    "Suwon": 41.5,
    "Osan": 56.5,
    "Seojeongri": 66.5,
    "Pyeongtaek": 75.0,
    "Seonghwan": 84.4,
    "Cheonan": 96.6,
    "Sojeongni": 107.4,
    "Jeonui": 114.9,
    "Jochiwon": 129.3,
    "Bugang": 139.8,
    "Sintanjin": 151.9,
    "Daejeon": 166.3,
    "Okcheon": 182.5,
    "Iwon": 190.8,
    "Jitan": 196.4,
    "Simcheon": 200.8,
    "Gakgye": 204.6,
    "Yeongdong": 211.6,
    "Hwanggan": 226.2,
    "Chupungnyeong": 234.7,
    "Gimcheon": 253.8,
    "Gumi": 276.7,
    "Sagok": 281.3,
    "Yangmok": 289.5,
    "Waegwan": 296.0,
    "Sindong": 305.9,
    "Daegu": 323.1,
    "Dongdaegu": 326.3,
    "Gyeongsan": 338.6,
    "Namseonghyeon": 353.1,
    "Cheongdo": 361.8,
    "Sangdong": 372.2,
    "Miryang": 381.6,
    "Samnangjin": 394.1,
    "Wondong": 403.2,
    "Mulgeum": 412.4,
    "Hwamyeong": 421.8,
    "Gupo": 425.2,
    "Sasang": 430.3,
    "Busan": 441.7,
}


def main():
    N, Q = map(int, input().split())

    arrival: dict[str, Time] = {}
    departure: dict[str, Time] = {}

    for _ in range(N):
        name, arr, dep = input().split()

        arrival[name] = Time.parseTime(arr)
        departure[name] = Time.parseTime(dep)

    for _ in range(Q):
        start, end = input().split()

        t = departure[start].getDuration(arrival[end])

        print(abs(dist[end] - dist[start]) / int(t) * 60)


main()

G. 용액 합성하기

골드 V 골드 V

두 포인터로 $\mathcal{O}(N)$에 해결할 수 있습니다.

$l = 0$, $r = N - 1$로 초기화합시다.

$A_l + A_r < 0$인 경우 합을 늘려야 하므로 $l$을 증가시킵니다.

$A_l + A_r > 0$인 경우 합을 줄여야 하므로 $r$을 감소시킵니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def main():
    N = int(input())
    A = list(map(int, input().split()))

    l = 0
    r = N - 1

    ans = A[0] + A[1]

    while l < r:
        if abs(A[l] + A[r]) < abs(ans):
            ans = A[l] + A[r]

        if A[l] + A[r] < 0:
            l += 1
        else:
            r -= 1

    print(ans)


main()

번외로, 이분 탐색으로도 해결할 수 있습니다.

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
def upper_bound(arr: list, target) -> int:
    lo = 0
    hi = len(arr)

    while lo < hi:
        m = (lo + hi) >> 1

        if arr[m] <= target:
            lo = m + 1
        else:
            hi = m

    return lo


def main():
    N = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        if A.count(0) >= 2:
            print(0)
            return

    ans = A[0] + A[1]

    for i in range(N):
        if A[i] == 0:
            continue

        j = upper_bound(A, -A[i])

        if 0 <= j - 1 and j - 1 != i and abs(A[i] + A[j - 1]) < abs(ans):
            ans = A[i] + A[j - 1]
        if j < N and j != i and abs(A[i] + A[j]) < abs(ans):
            ans = A[i] + A[j]

    print(ans)


main()

H. 배열 돌리기 2

골드 V 골드 V

$(i, j)$에 있는 수를 $(i, j + c)$로 옮기고 나머지를 왼쪽으로 한칸씩 당기는 방법을 생각해 봅시다.

$(i, j)$와 $(i, j + 1)$를 교환하고, $(i, j + 1)$와 $(i, j + 2)$를 교환하고… 를 반복하면 됩니다.

따라서 반시계방향으로 회전하는 것은 시계방향으로 교환하는 행위와 같습니다.

회전해야 할 길이로 $R$을 나눈 나머지만큼 회전하면 시간 복잡도 $\mathcal{O}(N^3)$ 정도에 해결할 수 있습니다.

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
def main():
    N, M, R = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    def rotate(start: tuple[int, int], end: tuple[int, int], dr: int, dc: int):
        r, c = start
        while (r, c) != end:
            nr = r + dr
            nc = c + dc

            A[r][c], A[nr][nc] = A[nr][nc], A[r][c]

            r, c = nr, nc

    r, c = 0, 0
    while r < N - 1 - r and c < M - 1 - c:
        cnt = R % (2 * (N - 2 * r) + 2 * (M - 2 * c) - 4)

        for _ in range(cnt):
            rotate((r, c), (r, M - 1 - c), 0, 1)
            rotate((r, M - 1 - c), (N - 1 - r, M - 1 - c), 1, 0)
            rotate((N - 1 - r, M - 1 - c), (N - 1 - r, c), 0, -1)
            rotate((N - 1 - r, c), (r + 1, c), -1, 0)

        r += 1
        c += 1

    for row in A:
        print(*row)


main()

랜덤 마라톤 · 코스 72