[백준 | BOJ] 숙명여자대학교 SMUPC 풀어보기

13시부터 17시까지 4시간짜리 오픈콘테스트가 열렸는데, 다른 문제 푸느라 30분동안밖에 못 풀었다.

오늘 돼서 아침에 문제 훑어보고 풀이. 무난하고 재밌었던 문제셋이지만, 한 쪽에 치우쳐진 알고리즘 셋이라는 점이 아쉽다.

 

제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC) Open

30분동안 이것저것 건드리다가 두 문제밖에 해결하지 못 했다..

업솔빙 결과

---

21734: SMUPC의 등장

각 알파벳의 아스키 코드를 구한 뒤에, 각 자리수를 더한 만큼 알파벳을 출력하면 된다.

for i in input():
    print(i * sum(list(map(int, list(str(ord(i)))))))

 

21735: 눈덩이 굴리기

dp로 풀다가 시간까지 저장을 어떻게 하지,, 라는 생각에 대회날에는 넘기고 아침에 다시 보니 dfs로 파고내려가면 됐던 문제.

dfs(위치, 시간, 현재 크기) 로 두고 시간이 다 되면 최대값 갱신하고 리턴하는 방식으로 풀었다. dp에 너무 약해 나..

def f(n, t, sz):
    global ans
    if t < M:
        return
    if t <= M:
        ans = max(ans, sz)
    if n <= N-1:
        f(n+1, t+1, sz+snow[n+1])
    if n <= N-2:
        f(n+2, t+1, sz//2 + snow[n+2])
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
snow = [0] + list(map(int, input().split()))
ans = -1
f(0, 0, 1)
print(ans)

 

21736: 헌내기는 친구가 필요해

그래프 dfs/bfs. I 칸에서부터 나아가면서 P 만날때마다 += 1 해주면 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1234568)
H, W = map(int, input().split())
a, b = -1, -1
g = []
for i in range(H):
    t = list(input())
    if 'I' in t:
        a, b = i, t.index('I')
    g.append(t)
 
v = [[0] * W for i in range(H)]
 
dy = 1, -1, 0, 0
dx = 0, 0, 1, -1
cnt = 0
def dfs(y, x):
    global cnt
    v[y][x] = 1
    for i in range(4):
        ty, tx = y + dy[i], x + dx[i]
        if not (0 <= ty < H and 0 <= tx < W):
            continue
        if v[ty][tx]:
            continue
        if g[ty][tx] == 'X':
            continue
        if g[ty][tx] == 'P':
            cnt += 1
        dfs(ty, tx)
 
dfs(a, b)
print(cnt if cnt else "TT")

 

21737: SMUPC 계산기

그냥 구현인데 런타임 받아서 꽤나 당황했던 문제. IndexError인 줄 알고 고쳐서 냈는데도 소용없길래, 다음날에 다시 돌려봤더니 ZeroDivisionError. 구현 상 편의로 받아둔 리스트에 [0]을 추가해뒀는데, 'U '가 마지막으로 들어오는 경우가 문제였다.

현재 인덱스를 가리키는 변수 하나 두고, SMUP 를 만나면 계산하고 +=2, C 를 만나면 출력하고 +=1.

인덱스가 넘어갈까봐 리스트에 빈값 하나 둔거였는데, 0 때문에 런타임 에러가 발생했던 거였다.

import sys

input = sys.stdin.readline

 

N = int(input())

t = input()

tmp = ""

g = []

for i in t:

    if i in "SMUPC":

        if tmp:

            g.append(int(tmp))

        g.append(i)

        tmp = ""

    else:

        tmp += i

g += [1]

ret = 0

idx = 0

ans = []

while idx

<

 len(g)-1:

    if type(g[idx]) == int:

        ret = g[idx]

        idx += 1

    else:

        c = g[idx]

        if c == "S":

            ret -= g[idx+1]

            idx += 2

        elif c == "M":

            ret *= g[idx+1]

            idx += 2

        elif c == "U":

            if ret < 0:

                ret *= -1

                ret //= g[idx+1]

                ret *= -1

            else:

                ret //= g[idx+1]

            idx += 2

        elif c == "P":

            ret += g[idx+1]

            idx += 2

        elif c == "C":

            ans.append(ret)

            idx += 1

print(*ans if ans else ["NO OUTPUT"])

 

21738: 얼음깨기 펭귄

dfs/bfs. 펭귄으로부터 가장 가까운 지지대 얼음 두 곳으로부터 펭귄을 잇는 길을 제외한 얼음은 제거해도 된다.

펭귄이 위치한 자리를 루트로 트리를 만들어준 다음에, 지지대로부터 DFS 수행하고, 펭귄이 도착하면 방문처리 전에 리턴했다.

두 가지 경로의 길이를 R1, R2 라고 하면 N - (R1 + R2 + 1). 펭귄이 위치한 곳도 무너지면 안 되니까.

import sys

input = sys.stdin.readline

 

sys.setrecursionlimit(1234567)

N, S, P = map(int, input().split())

# 1 ~ S 

P -= 1

 

g = [[] for i in range(N)]

for i in range(N-1):

    a, b = map(int, input().split())

    g[a-1].append(b-1)

    g[b-1].append(a-1)

route = []

v = [0] * N

def dfs(n, d):

    if n == P:

        route.append(d)

        return

    v[n] = 1

    for nxt in g[n]:

        if not v[nxt]:

            dfs(nxt, d+1)

 

for i in range(S):

    dfs(i, 0)

route.sort()

print(N - route[0] - route[1] - 1)

 

21739: 펭귄 네비게이터

문제를 조금 변형하면 올바른 괄호 문자열의 개수를 구하는 문제인데,, (위에 2N 개 중 N 개 고른 뒤, 아래에는 무조건 위보다 큰 수가 와야 한다)

카탈란 수를 구하는 문제가 된다. 2n C n 을 (n+1)로 나누는 게 일반항. 하나씩 나눠가면서 풀었는데 math.comb가 있었다,, 파이썬 최고

import sys

MOD = int(1e9) + 7

def b(n, k):

    ret = 1

    if k > n-k:

        k = n-k

    for i in range(k):

        ret *= (n-i)

        ret //= (i+1)

    return ret

def f(n):

    c = b(2*n, n)

    return c//(n+1)

print(f(int(input()))%MOD)

 

21740: 도도의 수학놀이

이건 아직 못 풀었다. 문제가 그리디하게 생겼는데, 숫자들을 정렬하는 방법을 조금 더 생각해봐야 할 듯.

단 하나의 수를 두 번 쓸 수 있다는 점에서 생각해야할 게 늘었다.

꽤 많은 시도 끝에 성공했다 !

하나의 수를 두 번 쓸 수 있는데, 이 수는 일단 자리수가 커야 하고, 자리수가 같으면 뒤집었을 때 값이 커야 한다.

수들을 받아서 일단 뒤집고, 두 번 쓸 수를 뽑기 위해 정렬해서 배열에 추가해준다.

(s1+s2>s2+s1) 을 기준으로 정렬해주면 가장 큰 수가 나오는데, 이를 다시 뒤집어주면 원래 상태가 된다.

파이썬에서는 정렬할 때 자신이 원하는 방법으로 정렬하기 위해 매개변수로 key 를 받는다.

functools.cmp_to_key 를 통해 compare 함수를 key 에 넣어줬다.

(진짜 많이 틀렸는데, 2를 돌리면 당연히 5라고 생각했다.. 문제에도 준 내용인데, 문제는 꼭 처음부터 정독하자)

from functools import cmp_to_key

import sys

input = sys.stdin.readline

 

def cmp(s1, s2):

    a, b = s1+s2, s2+s1

    return 1 if a

>

b else 0 if a==b else -1

    

def cmp2(s1, s2):

    la, lb = len(s1), len(s2)

    if len(s1) == len(s2):

        a, b = int(s1), int(s2)

        return 1 if a

>

b else 0 if a==b else -1

    return 1 if la

>

lb else 0 if la==lb else -1

    

convert = {"0":"0", "1":"1", "2":"2", "5":"5", "6":"9","8":"8","9":"6"}

 

def rev(n):

    ret = ''

    for i in n[::-1]:

        ret += convert[i]

    return ret

 

N = int(input())

arr = input().split()

 

a = [rev(x) for x in arr]

a.sort(key=cmp_to_key(cmp2))

a += [a[-1]]

a.sort(key=cmp_to_key(cmp))

 

ans = ""

for i in a:

    ans += rev(i)

print(ans)

 

시간 쫓기니까 풀 것도 못 풀게 된다.

고급 알고리즘 연습하는것보다는 작은 대회에서 무난하게 풀 수 있을정도로 solved.ac 기준 S1 - G2정도 문제 연습을 목표로 연습해야지