[랜덤 마라톤] 랜덤 마라톤 코스 16

 

 

 

랜덤 마라톤 문제를 한두 문제 풀어본 적은 있는데, 제대로 다 풀기 시작한 것은 이번이 처음인 것 같아서 정리해서 올려본다.

 

A. Divide the Cash

해결 : 24/09/18

전체 금액을 문제에서 주어진 비율대로 비례 배분하는 문제. 간단하다.

# 25858번 Divide the Cash
# 사칙연산
N, D = map(int, input().split())
A = list(int(input()) for _ in range(N))
T = sum(A)
for i in A:
    print(i*D//T)

 

B. Going to the Movies

해결 : 24/09/18

제한 $C$를 넘지 않으면서 합을 최대로 만드는 문제. 제한이 커지면 냅색으로 해결할 수 있을 것 같다.

여기에서는 $N$이 최대 $16$이어서, 브루트포스로도 해결할 수 있다. 오랜만에 파이썬에서 zfill함수를 써본 것 같다.

# 6187번 Going to the Movies
# 브루트포스
'''
접근 방법:
최대 16마리고, 걍 브루트포스로 탐색
'''
import sys
input = sys.stdin.readline

ans = 0
C, N = map(int, input().split())
A = [int(input()) for _ in range(N)]
for i in range(2**N):
    bitstring = bin(i)[2:].zfill(N)
    S = 0
    for j in range(N):
        if bitstring[j] == '1':
            S += A[j]
    if S <= C and ans < S:
        ans = S
print(ans)

 

C. 카드 놓기

해결 : 24/09/18

덱으로 해결한다는 생각을 못해서, 주어진 정보를 통해 역으로 구성하는 식으로 구현했다.

예를 들어, 예제 입력 2와 같은 경우 2 3 3 2 1로 나와 있는데, 5를 답 배열에서 현재 비어있는 자리 중에서 위에서 2번째 자리에 넣고, 그 다음은 3으로 나와있으므로, 4를 현재 비어있는 자리 중 제일 아래 자리에 넣고...

이런 식으로 구현했다.(예제의 정답은 1 5 2 3 4 이다.)

비어있는 자리 중 가장 위를 나타내는 포인터 F, 두번째 위를 나타내는 포인터 S, 가장 아래를 나타내는 포인터 R을 선언하고, 실제 숫자를 끼워넣는 방식으로 했다.

이미 끼워진 자리는 vis배열을 통해 끼워져있다는 것을 표현했다.

두번째 위를 나타내는 포인터 S를 옮기는 작업이 꽤 까다로웠다. F는 그냥 옮겨도 시간 초과가 나지 않는데, F와 S 사이는 서로 크게 떨어져 있을 수 있기 때문에 S를 F+1로 선언하는 것은 위험하다.(이것 때문에 한번의 TLE를 받았다.)

S를 max(S, F+1)로 선언하면 시간 초과를 받지 않을 수 있다.

# 18115번 카드 놓기
# 시뮬레이션, 구현
'''
접근 방법:
역으로 만들자
'''
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
vis = [0 for _ in range(N)]
ans = [0 for _ in range(N)]
F, S, R = 0, 1, N-1
for i in range(N):
    order, num = A[i], N-i
    if order == 1:
        while F < N and vis[F] != 0:
            F += 1
        vis[F] = 1
        ans[F] = num
    elif order == 2:
        while F < N and vis[F] != 0:
            F += 1
        S = max(F+1, S)
        while vis[S] != 0:
            S += 1
        vis[S] = 1
        ans[S] = num
    else:
        while R >= 0 and vis[R] != 0:
            R -= 1
        vis[R] = 1
        ans[R] = num
print(*ans)

 

D. Shuffle

해결 : 24/09/19

string의 permutation이 주어질 때, 이를 $N$번 반복한 후의 string을 구하는 문제.

파이썬은 maketrans를 통해 대치 테이블을 만들고, translate를 통해 한 번의 permutation을 직접 수행할 수 있다.

처음엔 나이브하게 그냥 $N$번 반복했으나, $N$의 제한이 최대 20억인것을 발견하고 수정했다.

permutation을 반복하면 원래 문자열로 돌아오는 주기 $o$가 있는데, 이 주기가 되었다면 즉시 멈추고 문자열을 $N \% o$번만 permutation을 하면 된다.

# 6809번 Shuffle
# 문자열
'''
접근 방법:
str.maketrans + translate
'''
import sys
input = sys.stdin.readline

table = str.maketrans(''.join(chr(i) for i in range(65, 91))+'_', ''.join((input().rstrip() for _ in range(27))))
N = int(input())
S = input().rstrip()
Original = S
orbit = 1
for i in range(N):
    S = S.translate(table)
    if S == Original:
        orbit = i+1
        break
for i in range(N%orbit):
    S = S.translate(table)
print(S)

 

E. 용돈 관리

해결 : 24/09/19

문제를 정리하면, 길이 $N$의 배열 $A$를 연속되게 $M$개 ($A_1, A_2, \dots, A_M$)로 분할 후, $\min ( \text{sum}(A_i))$를 구하는 문제이다.

처음에는 DFS를 사용하여 탑다운 DP를 할까 생각했었다. 들고가는 정보는 배열의 길이, 지금까지 쓴 금액, 분할한 횟수 정도로 생각했는데, 생각보다 고려할 게 많아져서 다른 길로 틀었다.

최솟값 문제임을 보고 이분 탐색을 생각했고, Parametric search로 해결했다. 중간에 인덱스 실수, 구현 미스 등으로 3번 정도 틀렸다.

# 6236번 용돈 관리
# 이분 탐색
'''
접근 방법:
잘 모르겠는데 이분탐색 하면 되지 않을까
흠
시복도는 10만*log(10억)
먼가 먼가임 괜찮을것 같기도
'''
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(int(input()) for _ in range(N))
s, e = 1, 10000*100_000*10
while s < e:
    m = (s+e)//2
    cnt, t = 1, 0
    flag = False
    for i in range(N):
        t += A[i]
        if t > m:
            t = A[i]
            if t > m:
                flag = True
                break
            cnt += 1
    if flag:
        s = m+1
        continue
    if cnt <= M:
        e = m
    else:
        s = m+1
print(s)

 

F. 감시 피하기

해결 : 24/09/19

간단한 구현 + 백트래킹이다. 선생은 4방향을 볼 수 있고 장애물에 막히면 그 뒤는 못본다. 선생이 학생을 못보도록 장애물 3개를 설치할 수 있다면 'YES'를, 아니면 'NO'를 출력하면 된다.

파이썬의 combinations + 장애물이 놓인 상황에서 선생이 학생을 볼 수 있는 지의 여부 판단 함수를 통해 쉽게 구현했다.

# 18428번 감시 피하기
# 브루트포스, 구현
'''
접근 방법:
걍 N^2C3해서 뽑고 직접 판단하면 될듯
'''
import sys
from itertools import combinations
input = sys.stdin.readline

def judge(graph):
    N = len(graph)
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 'T':
                for k in range(4):
                    nr, nc = i, j
                    while 0 <= nr < N and 0 <= nc < N:
                        if graph[nr][nc] == 'S':
                            return False
                        if graph[nr][nc] == 'O':
                            break
                        nr, nc = nr+dr[k], nc+dc[k]
    return True

def main():
    N = int(input())
    graph = list(input().rstrip().split() for _ in range(N))
    s = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 'X':
                s.append((i, j))
    for tpl in combinations(s, 3):
        for i, j in tpl:
            graph[i][j] = 'O'
        if judge(graph):
            print('YES')
            return
        for i, j in tpl:
            graph[i][j] = 'X'
    print('NO')
    return

main()

 

G. 바둑이 포커

해결 : 24/09/19

약간 귀찮은 정렬 + 구현 문제다.

정렬 조건은 문제에 다 나와있고, 카드가 6장 밖에 안주어져서 나는 나이브하게 $\mathcal{O}(N^2)$정렬을 짰다.

정렬 조건이 크게 2개여서 정렬 조건 함수도 2개로 나눴다.

같은 서열인 경우에 우위를 따지는 조건은 많은 조건 분기 + 깡 구현으로 해결했다. 더 똑똑하게 구현하는 방법은 생각이 안났다. 조금 귀찮았던 점은 16진수로 주어졌다는 점이다.

# 17292번 바둑이 포커
# 정렬, 구현
'''
접근 방법:
걍 하면 될듯
'''
import sys
input = sys.stdin.readline

def order(pair:str):
    num1, color1, num2, color2 = pair
    if (int(num1,16)+1)%15 == int(num2,16)%15:
        return 1
    if (int(num1,16)-1)%15 == int(num2,16)%15:
        return 1
    if int(num1,16)%15 == int(num2,16)%15:
        return 2
    return 3

def order_again(pair1:str, pair2:str):
    num1, color1, num2, color2 = pair1
    num3, color3, num4, color4 = pair2
    is_same_color1 = (color1 == color2)
    is_same_color2 = (color3 == color4)
    if is_same_color1 ^ is_same_color2:
        if is_same_color1:
            return False
        else:
            return True
    pair1_max_num = max(int(num1,16), int(num2, 16))
    pair2_max_num = max(int(num3,16), int(num4, 16))
    if pair1_max_num > pair2_max_num:
        return False
    if pair1_max_num < pair2_max_num:
        return True
    pair1_min_num = min(int(num1,16), int(num2, 16))
    pair2_min_num = min(int(num3,16), int(num4, 16))
    if pair1_min_num > pair2_min_num:
        return False
    if pair1_min_num < pair2_min_num:
        return True
    max_num_col1, max_num_col2 = None, None
    if int(num1,16) > int(num2, 16):
        max_num_col1 = color1
    elif int(num1,16) < int(num2, 16):
        max_num_col1 = color2
    else:
        if color1 == 'b': max_num_col1 = color1
        elif color2 == 'b': max_num_col1 = color2
        else: max_num_col1 = color1
    if int(num3,16) > int(num4, 16):
        max_num_col2 = color3
    elif int(num3,16) < int(num4, 16):
        max_num_col2 = color4
    else:
        if color3 == 'b': max_num_col2 = color3
        elif color4 == 'b': max_num_col2 = color4
        else: max_num_col2 = color3
    if max_num_col1 == 'b':
        return False
    return True

card = input().rstrip().split(',')
pairs = [card[i]+card[j] for i in range(6) for j in range(i+1, 6)]
for i in range(15):
    for j in range(i+1, 15):
        p1, p2 = pairs[i], pairs[j]
        if order(p1) > order(p2):
            pairs[i], pairs[j] = pairs[j], pairs[i]
        elif order(p1) == order(p2):
            if order_again(p1, p2):
                pairs[i], pairs[j] = pairs[j], pairs[i]
print(*pairs, sep='\n')

 

H. Huge Numbers

해결 : 24/09/19

$A^{N!} \text{mod } P$를 구하는 문제. 각 제한은 최대 10만이다.

40초의 수상하게 큰 제한을 보고 그냥 pow($A$, $N!$, $P$)를 제출했더니 맞았다.(황당...)

# 24009번 Huge Numbers
# 수학
'''
접근 방법:
걍 하면 되지 않을까
숫자가 좀 큰데
일단 믿음을 가지고 ㄱㄱ
'''
import sys
input = sys.stdin.readline
from math import factorial

def solve():
    A, N, P = map(int, input().split())
    return pow(A, factorial(N), P)

T = int(input())
for i in range(1, T+1):
    print(f'Case #{i}: {solve()}')