2023 02 17 problem solving

생각보다 문제의 풀이를 작성하는것이 재밌어서 앞으로 자주 할 것 같다.

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

2629번: 양팔저울

간단한 배낭 dp 문제이다. 

dp(i, j)를 i번까지 추를 사용해서 무게 j를 만들 수 있는가? 로 정의하자.

구슬의 무게를 확인할 수 있다는 것이 무슨 뜻일까? 구슬을 왼쪽 저울에 고정한다 할 때, 오른쪽에 추를 올리는것은 추의 무게를 더한다고 할 수 있고, 왼쪽에 추를 올리는 것은 추의 무게를 뺀다 할 수 있다.

dp(0, 0)은 추를 사용하지 않고 무게가 0인지 확인할 수 있기에 참으로 지정해주자.

dp(i-1, j)가 가능하다면, dp(i, j) (i번째 추를 사용하지 않는 경우), dp(i, j - w[i]) (i번째 추를 왼쪽에 두는 경우), dp(i, j + w[i]) (i번째 추를 오른쪽에 두는 경우)가 가능하다.

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a = [0] + a

dp = [[1] + [0] * 40000 for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(40001):
        if dp[i - 1][j]:
            if j + a[i] < 40001: dp[i][j + a[i]] = 1
            if j - a[i] >= 0: dp[i][j - a[i]] = 1
            if a[i] - j >= 0: dp[i][a[i] - j] = 1
            dp[i][j] = 1

Q = int(input())
b = list(map(int, input().split()))
for ball in b:
    if dp[n][ball]: print("Y", end=' ')
    else: print("N", end=' ')

 

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

11967번: 불켜기

실수하기 쉬운 DFS 문제이다. 단순히 dfs를 돌면서 현재 정점에서 킬 수 있는 모든걸 켜주면 될거같다고 해서 구현했는데.. 틀렸다. 단순히 키는것이 아니라, 불을 킨 좌표 상하좌우에 방문한적이 있는 노드가 있으면 불을 킨 곳에서 dfs를 또 돌려줘야한다. 이러면 위치에서 상하좌우로 이동할때 가능한것이 3가지가 있다. 1. 불이 켜져있어 이동할 수 있다. 2. 불이 꺼져있고 앞으로도 꺼져있을거기에 이동할 수 없다. 3. 불이 꺼져있지만 나중에 불이 켜진다. 3번의 경우에는 나중에 불을 킬때 탐색을 해주니 모든 경우의 수를 수행할 수 있다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

dydx = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def dfs(x, y):
    global ans
    visited[x][y] = 1
    for i, j in g[x][y]:
        if not cango[i][j]: ans += 1
        cango[i][j] = 1
        if not visited[i][j]:
            for dy, dx in dydx:
                nx = i + dx
                ny = j + dy
                if 0 < nx <= n and 0 < ny <= n:
                    if visited[nx][ny]: 
                        dfs(i, j)
                        break
    for dy, dx in dydx:
        nx = x + dx
        ny = y + dy
        if 0 < nx <= n and 0 < ny <= n:
            if not visited[nx][ny] and cango[nx][ny]: dfs(nx, ny)

n, m = map(int, input().split())
g = [[[] for j in range(n + 1)] for i in range(n + 1)]

for _ in range(m):
    x, y, a, b = map(int, input().split())
    g[x][y].append((a, b))

visited = [[0] * (n + 1) for _ in range(n + 1)]
cango = [[0] * (n + 1) for _ in range(n + 1)]
cango[1][1] = 1
ans = 1
dfs(1, 1)
print(ans)

 

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

11968번: High Card Wins

그냥 카드를 정렬해주고 그리디하게 사용해주면 된다. 어렵지 않다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
a = [i for i in range(2 * n + 1)]
b = []
for i in range(n):
    b.append(int(input()))
    a[b[-1]] = 0
a.sort()
b.sort()
a = deque(a)
b = deque(b)
ans = 0
while a:
    while a and a[0] <= b[0]: a.popleft()
    if a:
        ans += 1
        a.popleft()
        b.popleft()

print(ans)

 

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

11969번: Breed Counting

누적합 기초 문제이다. 누적합의 존재를 까먹어서 구간합 세그를 짜다 뇌절인걸 깨닫고 빠르게 고쳤다.

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = [0] + [int(input()) for _ in range(n)]
psum = [[0, 0, 0, 0] for _ in range(n + 1)]
for i in range(1, n + 1):
    psum[i] = psum[i - 1][:]
    psum[i][a[i]] += 1

for _ in range(q):
    l, r = map(int, input().split())
    tmp = psum[r][:]
    tmp[a[l]] += 1
    print(tmp[1] - psum[l][1], tmp[2] - psum[l][2], tmp[3] - psum[l][3])

 

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

11996번: Circular Barn (Silver)

실수하기 쉬운 구현 문제이다. 실제로 실수해서 3번 정도 틀렸다. 배열에 소의 최소 위치를 저장해주고, 옆으로 밀어주면 된다. 말로 이해하는 것 보다 코드로 이해하는 것이 더 쉬울 것 같다.

import sys
input = sys.stdin.readline

def sigma(l, r): return (r * (r + 1) * (2 * r + 1)) // 6 - (l * (l + 1) * (2 * l + 1)) // 6 + l * l

n = int(input())
c = [int(input()) for _ in range(n)]
a = [i for i in range(n)]
for i in range(1, n):
    l = i - 1
    a[i] = max(a[i], a[l] + c[l])
ans = 0
for i in range(n):
    l = i - 1
    a[i] = max(a[i], (a[l] + c[l]))
    if c[i] > 0: ans += sigma((a[i] - i) % n, (a[i] - i) % n + c[i] - 1)
print(ans)

a[i] 에는 i번째 문으로 들어오는 소 중 가장 늦게 들어오는 소의 위치가 저장된다. 이 위치가 전의 소보다 더 작으면 안되기 때문에 옆으로 밀어준다. 원형이기때문에 한번 더 밀어주고, 제곱수의 합 공식을 이용해 처리해주면 된다.