랜덤 마라톤 코스(43)

이번 주 solved.ac 랜덤 마라톤 문제들의 간단한 풀이이다. 25.03.29 카페에서 본공부 전 간단하게 진행하였다.

9947 Coin tossing

Bronze 2 난이도의 문제로 매우 간단한 문제였다.

입력으로 들어오는 n개의 H,T에 대하여 같은 경우 앞 사람이 점수를 먹고, 다르면 뒷 사람이 점수를 먹는 형식이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 import sys
input = sys.stdin.readline

while True :
    _in = list(map(str,input().split()))
    if _in == ['#', '#']:
        exit()
    n = int(input())
    x,y = 0,0
    for _ in range(n) :
        a, b = map(str,input().split())
        if a == b:
            x += 1
        else :
            y += 1
    print(f'{_in[0]} {x} {_in[1]} {y}')

31738 매우 어려운 문제

정수 N,M에 대하여 N! % M을 구하는 문제이다.

처음에 정말 단순히 math.factorial(n) % m을 통해 풀었다가 너무 당연하게도 시간초과를 받았다.

문제의 제한을 보면 N이 $10^{18}$, M이 $10^{17}$인 것을 확인할 수 있다. 간단한 DP를 통해 나머지를 관리해주자.


1
2
3
4
5
6
7
8
9
10
11
12
13
 import sys
import math
input = sys.stdin.readline

n, m = map(int,input().split())
if n >= m :
    print(0)
    exit()
else :
    dp = [1]*(n+2)
    for i in range(1, n+1) :
        dp[i] = (dp[i-1] * i)%m
    print(dp[n])

5078 Shirts

셔츠들을 입력을 받아서 사이즈, 색깔 별로 정렬하여 출력하는 간단한 문제였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 import sys
input = sys.stdin.readline

while True :
    n = int(input())
    if not n :
        # work
        exit()
    
    shirts = []
    for _ in range(n) :
        s = input().strip()
        shirts.append(s)
    m = int(input())
    for _ in range(m) :
        s = input().strip()
        shirts.append(s)
    shirts.sort(key=lambda x : (-ord(x[0]), ord(x[1])))
    print(*shirts)

1448 삼각형 만들기

괜찮은 함정(?) 문제 였다.

괜찮다고 생각했던 부분중 하나는 세 변의 길이의 합이 최댓값을 구하고 싶다. 라는 부분과 삼각형을 이룰 수 있는 성질이 합쳐지면 매우 Greedy한 문제로 변한다는 부분이었다.

결국

\[a + b > c, a + c > b, b + c > a\]

를 만족해야 하는 것이며 단순히 정렬하여 맨 위 index부터 연속된 3개의 숫자가 삼각형을 이룰 수 있는 조건인지 찾으면 되는 매우 간단한 문제로 변한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]
arr.sort(reverse=True)
idx = 0
while idx + 2 < n :
    a,b,c = arr[idx], arr[idx+1], arr[idx+2]

    if a + b > c and b + c > a and a + c > b :
        print(a+b+c)
        exit()
    else :
        idx += 1

print(-1)

18126 너구리 구구

무려 7번이나 틀린 문제이다…

총 1부터 N개로 N개의 방으로 이루어진 곳에서 N-1개의 길로 서로 오갈 수 있다고 한다. 이 때 입구에서 가장 먼 방에 아이스크림을 숨기려고 한다.

당연히 가장 멀다길래 N번방 까지의 거리일 줄 알았지만 길들의 거리를 모두 계산하고 1번부터 가장 멀리 떨어진 방까지의 거리를 출력하는 것이 문제였다.

왜 틀렸지? 라는 생각이 든다면 문제를 다시 한 번 확인해보자.


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
 import sys, heapq
from collections import deque
input = sys.stdin.readline

def bfs(start) :
    heap = []
    heapq.heappush(heap, (0, start))

    while heap :
        cost, x = heapq.heappop(heap)

        if cost > dist[x] :
            continue

        for nx, ncost in edge[x] :
            next_cost = cost + ncost
            if dist[nx] > next_cost :
                dist[nx] = next_cost
                heapq.heappush(heap, (next_cost, nx))
edge = [[] for _ in range(n+1)]
dist = [1e20 for _ in range(n+1)]
dist[0] = 0
dist[1] = 0
for _ in range(n-1) :
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
bfs(1)
print(max(dist))

2784 가로 세로 퍼즐

실버2 같은 느낌은 아니었지만 이번에도 꽤 괜찮은 문제였다.

6개의 단어가 주어지면 해당 6개의 단어로 $3X3$ 가로 세로 퍼즐을 만들 수 있냐라는 문제이다.

입력으로 주어지는 단어 수가 6개로 고정되어 있고 6개중 3개로 단어의 경우의 수를 뽑는 것은 시간적으로 매우 여유있기 때문에 permutations을 이용해 뽑아주었다.

괜찮다고 생각했던 부분은 그냥 재밌었기 때문이다.


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
 import sys
from itertools import permutations as pm
input = sys.stdin.readline

word = [input().rstrip() for _ in range(6)]
lst = list(pm(range(0,6), 3))

for i in lst :
    another = []
    org = [word[j] for j in i]
    for j in range(6):
        if j not in i :
            another.append(word[j])
    vertical = []
    for j in range(3) :
        tmp = ''
        for k in range(3) :
            tmp += org[k][j]
        vertical.append(tmp)
    vertical.sort()
    cnt = 0
    for j in range(3) :
        if vertical[j] == another[j] :
            cnt += 1
    if cnt == 3 :
        for row in i :
            print(word[row])
        exit()
    
print(0)

14426 접두사 찾기

실버1 트라이 문제이지만 단순히 접두사로 올 수 있는 모든 경우의 수를 set형에 넣어두고 check하는 것으로도 풀이가 가능하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 import sys
input = sys.stdin.readline

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

c = set()
for i in range(n) :
    s = input().rstrip()
    t = ''
    for j in s :
        t += j
        c.add(t)
a = 0
for i in range(m) :
    s = input().rstrip()
    if s in c :
        a += 1

print(a)

25343 최장 최장 증가 부분 수열

Gold 5 난이도의 LIS(Longest Increasing Subsequence) 문제이다.

최장 부분 수열의 문제를 2차원 version인데 다행히도 난이도를 낮추기 위한 최단거리라는 제한이 주어져 있다. (사실 최단거리가 아니면 어떻게 될지 난 모르긴함.)

기본 LIS의 틀인 DP를 통해 이전의 값들 보다 크다면 해당 DP를 업데이트 하는 방식 이었다. 점화식으로 보자면

\[dp[i] = max(dp[i], dp[j] + 1) \quad if \quad (arr[i] > arr[j] \quad and \quad i > j)\]

약간 헷갈릴 수 있는 부분으로 원래 1차원 LIS의 공식은 $i = range(1,n)$, $j = range(i)$ 였었다. 하지만 2차원 LIS에서 바뀐 이유는 같은 열 같은 행이면서 이전의 값이 있을 수 있기 때문에 범위를 아래 코드와 같이 수정해줘야 한다는 부분이다. 이부분은 재미있으면서도 좋은 부분인 것 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 import sys
input = sys.stdin.readline

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

dp = [[1 for _ in range(n)] for _ in range(n)]

for i in range(n) :
    for j in range(n) :
        for k in range(i+1) :
            for t in range(j+1) :
                if arr[i][j] > arr[k][t] :
                    dp[i][j] = max(dp[i][j], dp[k][t] + 1)

ans = 0
for i in range(n) :
    ans = max(ans, max(dp[i]))

print(ans)