Gumgood  
CP Algorithm

2022 서강대학교 프로그래밍 경시대회 Champion 부문 - Python 정답 코드

By Sangwon Lee Posted Dec 11, 2022

대회 문제는 백준 온라인 저지에 공개되어있다. https://www.acmicpc.net/category/697

A. 완전한 수열 (BOJ 26090)

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

import sys

input = lambda: sys.stdin.readline().strip('\n')


def solve():
    def p(x):
        for d in range(2, x):
            if x % d == 0:
                return False
            if x < d * d:
                break
        return x > 1

    ret = 0
    for i in range(n):
        for j in range(i, n):
            ret += p(j - i + 1) and p(sum(a[i:j + 1]))
    return ret


for T in range(1):
    n = int(input())
    a = list(map(int, input().split()))
    print(solve())

B. DPS (BOJ 26084)

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

import sys

input = lambda: sys.stdin.readline().strip('\n')


def solve():
    cnta = [0] * 256
    for it in a:
        cnta[ord(it[0])] += 1

    cnts = [0] * 256
    for it in s:
        cnts[ord(it)] += 1

    ret = 1
    for i, cnt in enumerate(cnts):
        if cnt == 1:
            ret *= cnta[i]
        elif cnt == 2:
            ret *= cnta[i] * (cnta[i] - 1) // 2
        elif cnt == 3:
            ret *= cnta[i] * (cnta[i] - 1) * (cnta[i] - 2) // 6
    return ret


for T in range(1):
    s = input()
    n = int(input())
    a = [''] * n
    for i in range(n):
        a[i] = input()
    print(solve())

C. 현대모비스 소프트웨어 아카데미 (BOJ 26091)

1
2
3
4
5
6
7
8
9
10
11
12
13
14

import sys

input = lambda: sys.stdin.readline().strip('\n')


def solve():
    a.sort()
    return sum([1 for i in range(n // 2) if a[i] + a[n - 1 - i] >= m])


for T in range(1):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve())

D. 수학적인 최소 공통 조상 (BOJ 26092)

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

import sys

input = lambda: sys.stdin.readline().strip('\n')


def solve(a, b):

    def lpf(p, x):
        for d in range(p, x):
            if not x % d:
                return d, x // d
            if d * d >= x:
                break
        return x, 1

    pa, pb = 2, 2
    while a != b:
        if a > b:
            pa, a = lpf(pa, a)
        else:
            pb, b = lpf(pb, b)
    return a


for T in range(1):
    a, b = map(int, input().split())

    print(solve(a, b))

E. 고양이 목에 리본 달기 (BOJ 26093)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import sys

input = lambda: sys.stdin.readline().strip('\n')


def solve():
    pmx = [0] * (k + 1)
    smx = [0] * (k + 1)
    for i in range(n):
        dp = [a[i][j] + max(pmx[j - 1], smx[j + 1]) for j in range(k)] + [0]
        for j in range(k):
            pmx[j] = max(pmx[j - 1], dp[j])
            smx[k - j - 1] = max(smx[k - j], dp[k - j - 1])
    return max(dp)


for T in range(1):
    n, k = map(int, input().split())
    a = [list(map(int, input().split())) + [0] for _ in range(n)]

    print(solve())

F. 더 어려운 스케줄링 (BOJ 26094)

Python에서 중간 원소 삭제를 지원하는 set 자료구조가 없다. 따라서 lazy하게 삭제를 수행하는 자료구조를 따로 구현했다.

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

import sys, heapq
from collections import deque

input = lambda: sys.stdin.readline().strip('\n')


class mySet():
    def __init__(self, rev=False):
        self.q = []
        self.d = []
        self.rev = rev

    def push(self, x):
        heapq.heappush(self.q, -x if self.rev else x)

    def remove(self, x):
        heapq.heappush(self.d, -x if self.rev else x)

    def top(self):
        while self.q and self.d and self.q[0] == self.d[0]:
            heapq.heappop(self.q)
            heapq.heappop(self.d)
        return -self.q[0] if self.rev else self.q[0]

    def empty(self):
        while self.q and self.d and self.q[0] == self.d[0]:
            heapq.heappop(self.q)
            heapq.heappop(self.d)
        return not bool(self.q)


def solve():
    ret = []
    q, r = mySet(), mySet(rev=True)
    f, b = deque(), deque()
    for o, *p in qry:
        if o == 0:
            f.append(p[0])
        elif o == 1:
            for x in f + b:
                q.push(x)
                r.push(x)
            if not q.empty() and q.top() > r.top():
                q, r = r, q
            f.clear()
            b.clear()
        elif o == 2:
            q, r = r, q
            f, b = b, f
        elif o == 3:
            if f:
                ret.append(f.pop())
            elif not q.empty():
                ret.append(q.top())
                q.remove(ret[-1])
                r.remove(ret[-1])
            else:
                ret.append(b.popleft())
    return ret


for T in range(1):
    n, q = map(int, input().split())
    qry = [tuple(map(int, input().split())) for _ in range(q)]

    print('\n'.join(map(str, solve())))

G. Maximize MEX (BOJ 26095)

https://www.acmicpc.net/problem/19857와 동일한 방법으로 해결할 수 있다.

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

import sys

input = lambda: sys.stdin.readline().strip('\n')


def solve():
    def chk(l):
        res, nd = n - sum(c[1:l]), 0
        for i in range(1, l)[::-1]:
            if c[i] >= nd + 1:
                res += c[i] - (nd + 1)
            else:
                nd += (nd + 1) - c[i]
        return res > nd

    c = [0] * n
    for x in a:
        c[x] += 1

    s, e = 0, n + 1
    while s < e:
        m = (s + e) // 2
        if chk(m):
            s = m + 1
        else:
            e = m
    return s - 1


for T in range(1):
    n = int(input())
    a = list(map(int, input().split()))

    print(solve())

H. 슈퍼 블랙잭 (BOJ 26096)

상한이 $3E$를 넘지 않는데 $E$의 최대값이 $10,000$이므로 이분 탐색 범위를 $30,000$까지 잡아주면 된다.

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

import sys

input = lambda: sys.stdin.readline().strip('\n')
EPS = 1e-6


def solve():
    def f(f0):
        dp = [0.0] * 30001
        pdp = [0.0] * 30001
        for i in range(0, 30000)[::-1]:
            if i < s:
                dp[i] = min([1 + (pdp[i + 1] - pdp[i + aj + 1]) / aj for aj in a])
            else:
                dp[i] = 0 if i <= e else f0
            pdp[i] = dp[i] + pdp[i + 1]
        return dp[0] + EPS > f0

    l, r = 0, 30000
    while r - l > EPS:
        m = (l + r) / 2
        if f(m):
            l = m
        else:
            r = m
    return l


for T in range(1):
    d = int(input())
    a = list(map(int, input().split()))
    s, e = map(int, input().split())

    print(solve())

여담

이번 Champion 대회에서는 구현이 복잡한 알고리즘이 출제되지 않았다. 덕분에 모든 문제에 대해 파이썬으로 작성한 정답 코드를 작성할 수 있었다.

spc, python