2023 02 21 problem solving

속삭이듯 사랑을 노래하다 꼭 보세요.. 명작임

어제는 애니메이트를 다녀오느라 문제를 거의 못풀었다..

오늘은 4문제를 풀었다. 다 꽤 재밌는 문제였다고 생각한다.

 

https://www.acmicpc.net/problem/10166

10166번: 관중석

 

실행시간 1등 먹어서 기분이 좋다.

이 문제는 여러가지 풀이법이 존재한다. 유클리드 호제법을 사용한 O(d2 ^2 log d2) 정도의 풀이가 정해인것 같다. 나는 dp로 O(d2 log d2)에 풀었다. 

 

기본적인 관찰: 반지름이 r인 동심원에 대하여, 반지름이 r의 배수인 동심원들과 정확히 r개의 좌석이 겹친다.

 

d1을 1로 고정시켜보자. 그럼 2, 3, 4 .... d2 까지 1을 빼주고, 2, 4, 6, 8, 10, 12 ... d2 까지는 2를 빼주고.. 하면 될것같지만 그럼 한 좌석을 여러번 빼주게 된다. 해법은 간단한데, 그냥 x에 대하여 x의 배수들의 좌석을 관리해줄 때, 현재 x에서 남아있는 좌석만큼 빼주면 된다. 조금만 생각해보면 자명하다. 

 

그럼 이제 d1을 1로 고정시키지 않고 생각해보자. x의 배수들에 대해 겹치는 좌석을 빼줄 때, [d1, d2] 구간에 최초로 등장하는 x의 배수는 빼주면 안된다. 그렇기에 tmp라는 변수를 만들어주고, 거기에 [d1, d2] 구간에 최초로 등장하는 x 배수의 값을 저장해주면 된다. 그냥 구간에 두번째로 등장하는 x의 배수부터 관리해주면 된다고 생각할 수 있는데, 그럼 오류가 생긴다. d1 = 4, d2 = 8을 생각해보자. x = 2일때, d1의 값을 관리해주지 않는다면, 나중에 x = 4일때 초과로 빼주게 된다.

import math
d1, d2 = map(int, input().split())
a = [i for i in range(d2 + 1)]
tmp = 0
for i in range(1, d2 + 1):
    if d1 <= i * math.ceil(d1 / i) <= d2:
        if i < d1: tmp += a[i]
        for j in range(i + i, d2 + 1, i): a[j] -= a[i]
print(sum(a[d1:d2+1]) + tmp)

설명이 좀 많이 난잡하다. 그냥 코드를 읽으면 이해하기 쉽다. 코드는 상당히 간단하다.

조화수열의 합은 log로 수렴하기에, 시간 복잡도는 O(d2 log d2)가 나온다.

 

https://www.acmicpc.net/problem/14527

14527번: Paired Up

재밌는 usaco 문제이다. 처음에 문제를 잘못 이해하여 큰일날뻔 했다. 영어 독해 연습을 더 해야할 것 같다..

그냥 정렬하고 작은거랑 큰거랑 합쳐주면 된다. 자명(증명하기 귀찮음)하게 그리디로 풀린다. 

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
a.sort(key=lambda x:x[1])
l, r = 0, n - 1
ans = 0
while l <= r:
    pairs = min(a[l][0], a[r][0])
    if l == r: pairs //= 2
    cnt = a[l][1] + a[r][1]
    ans = max(ans, cnt)
    a[l][0] -= pairs
    a[r][0] -= pairs
    if a[l][0] == 0: l += 1
    if a[r][0] == 0: r -= 1
print(ans)

 

https://www.acmicpc.net/problem/15458

15458번: Barn Painting

트리 dp 문제다.

dp(i, j) = i를 루트로 하는 서브트리에서, i를 j로 칠했을때 가능한 경우의 수

라고 정리해자. 그럼 노드를 하나의 색으로 고정시키고, 자식들에서 그 색을 제외한 색으로 색을 칠하는 경우를 곱해주면 된다. 색이 이미 정해져있는 노드는 따로 신경써주면 된다. O(n)에 해결할 수 있다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
mod = int(1e9) + 7

def dfs(i):
    v[i] = 1
    if c[i] >= 0:
        dp[i] = [0, 0, 0]
        dp[i][c[i]] = 1
    for j in g[i]:
        if not v[j]:
            dfs(j)
            for k in range(3):
                dp[i][k] = ((dp[i][k] % mod) * ((sum(dp[j][:k]) + sum(dp[j][k+1:])) % mod)) % mod

n, k = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

c = [-1] * (n + 1)
for _ in range(k):
    a, b = map(int, input().split())
    c[a] = b - 1

dp = [[1, 1, 1] for _ in range(n + 1)] #dp(i, j) = i를 루트로 하는 서브트리에서, i를 j로 색칠했을 때 가능한 경우의 수
v = [0] * (n + 1)
dfs(1)
print(sum(dp[1]) % mod)

 

https://www.acmicpc.net/problem/2560

2560번: 짚신벌레

덱 dp로 풀 수 있다고 하는데, 나는 누적합 + dp로 풀었다. 

 

imos법을 알면 접근하기 쉽다. 대충 구간에 어떤 연산을 해주는걸 누적합을 이용해서 관리해주는 방법이다. 예를들어 [1, 4] 구간에 1을 더해주고 싶으면, imos[1] = 1, imos[5] = -1을 해주고, imos[i] += imos[i - 1]을 해주면서 누적합을 관리해주면 된다. 그럼 구간을 순회하면서 i에 대해 그 i에 얼마나 더하면 되는질 바로 알 수 있다. 알면 굉장히 편하다.

 

이제 문제를 풀어보자. dp(n) = n일에 존재하는 벌레의 개수, imos(n) = n일에 태어나는 벌레의 개수

라고 정의해주자. imos 배열은 위에서 설명했던 방법으로 관리해주면 된다. dp(n)에는 그 날에 태어나는 벌레의 개수를 더해주고, d 일 뒤에 빼주면 된다. 

 

m = 1000
a, b, d, n = map(int, input().split())

dp = [0] * (n + 1)
imos = [0] * (n + 1)

imos[0] = 1
imos[1] = -1
for i in range(n + 1):
    dp[i] += dp[i-1]
    dp[i] %= m
    imos[i] += imos[i - 1] #i일에 imos[i]개의 새로운 개체가 태어남
    imos[i] %= m
    dp[i] += imos[i]
    dp[i] %= m
    if i + d <= n:
        dp[i + d] -= imos[i] #d일 후에는 죽음
        dp[i + d] %= m
    if i + a <= n:
        imos[i + a] += imos[i]
        imos[i + a] %= m
    if i + b <= n:
        imos[i + b] -= imos[i] #[i+a, i+a+b) 구간 업데이트
        imos[i + b] %= m
print(dp[n])