Codeforces Round #536 (Div. 2) A ~ D

codeforces.com/contest/1106

Dashboard - Codeforces Round #536 (Div. 2) - Codeforces

 

풀은 문제: A, B, C, D

못 풀은 문제: E, F

 

난이도

A - 800

B - 1500

C - 900

D - 1500

E - 2100

F - 2400

 

 

 

B번 스크립트보고 바로 C번으로 도망쳤으나 C번을 풀고 B번으로 돌아와보니 의외로 쉬웠고, D번이 B번이랑 난이도가 같게 나왔는데 개인적으로 D가 B보다 더 어려운 것 같았다.

 

 

 

 

 

A. Lunar New Year and Cross Counting

 

이건 그냥 X모양 나오는 것인지 테두리를 제외한 나머지 영역을 확인하는 완전탐색 코드를 짜면 된다.

def main():
    def B(x,y):
        for i in range(4):
            nx, ny = x+kx[i],y+ky[i]
            if D[nx][ny] == '.': return 0
        return 1
 
    n = int(input())
    D = [input() for _ in range(n)]
    ans = 0
    for i in range(1,n-1):
        for j in range(1,n-1):
            if D[i][j] == 'X':
                ans += B(i,j)
    print(ans)

 

 

 

 

B. Lunar New Year and Food Ordering

 

앨리스가 n개 종류의 음식을 만들었는데 i번째 종류의 음식의 남은 개수는 a[i]이고, 해당 음식의 가격은 c[i]이다.

가게에 손님이 들어와서 음식을 주문하는데, 손님이 원하는 음식이 남아있으면 음식을 주고, 음식이 없으면 가장 싼 음식을 주면 된다. 이때 가장 싼 음식이 여러개 있을 때, 음식의 종류 index번호가 가장 작은 음식을 주면 된다고 한다. 하지만 손님이 음식을 주문하였는데 손님이 원하는 음식의 개수보다 남아있는 음식의 개수가 더 클 때, 남아있는 음식을 다 처리하고 돈을 받지 못하는 상황이 생길 수도 있다고 한다.

이때 앨리스가 받을 수 있는 돈이 얼마인지 구하면 되는 문제이다.

 

그래서 변수를 정리해보면 아래와 같다.

a[i] = i번째 음식의 남은 개수

c[i] = i번째 음식의 가격

t = 손님이 원하는 t번째 음식

d = 손님이 원하는 음식의 개수

 

그리고 문제를 풀기전에 가장 싼 음식을 주는 항목도 있으므로 [c[i], i]로 이루어진 배열을 하나 만들어서 c[i]를 기준으로 오름차순으로 정렬된 배열 q를 하나 만들어둔다.

그래서 가장 작은 값을 가진 가격은 q[0]이 될 수 있다.

 

이제 주문을 받을 때 여러가지 상황으로 나눌 수 있는데

1) 손님이 원하는 음식과 음식의 개수가 해당 음식의 남아있는 개수보다 작을 때

ans += c[i] * d

a[i] = a[i] - d

d = 0

 

2) 손님이 원하는 음식과 음식의 개수가 해당 음식의 남아있는 개수보다 크거나 같을 때

 

ans += c[t] * a[t]

d -= a[t]

a[t] = 0

 

(q에서 가장 작은 가격을 가진 음식의 번호는 q[0][1], 해당 음식의 남은 개수는 a[q[0][1]], 가격을 q[0][0] = c[q[0][1]]라고 할 때)

 

2-1) a[q[0][1]]이 d보다 크거나 같은 경우

ans += q[0][0] * d

a[q[0][1]] -= d

d = 0

만약 a[q[0][1]] = 0이 되었을 경우엔 q에서 q[0]를 빼버림

 

2-2) a[q[0][1]]이 d보다 작은 경우

ans += q[0][0] * a[q[0][1]]

a[q[0][1]] = 0

d -= a[q[0][1]]

q에서 q[0]를 빼버리고 d=0이 될 때까지 2-1과 2-2를 반복

 

 

이걸 그대로 코드로 짜면 아래와 같이 나온다.

 

def main():
    n,m=map(int,input().split())
    a = [*map(int,input().split())]
    c = [*map(int,input().split())]
    D = []
    for i in range(n):
        D.append([c[i],i])
    D.sort(key = lambda z: z[0])
    q = deque(D)
    for i in range(m):
        ans = 0
        t, d = map(int,input().split()); t-=1
        if a[t] > d:
            ans = d * c[t]
            a[t] -= d
            d = 0
        else:
            ans = a[t] * c[t]
            d -= a[t]
            a[t] = 0
            while q:
                if a[q[0][1]] >= d:
                    ans += c[q[0][1]] * d
                    a[q[0][1]]-=d
                    d = 0
                    if a[q[0][1]] == 0: q.popleft()
                    break
                else:
                    ans += c[q[0][1]] * a[q[0][1]]
                    d -= a[q[0][1]]
                    a[q[0][1]] = 0
                    q.popleft()
        if d > 0: print(0)
        else:print(ans)

 

 

 

 

 

C. Lunar New Year and Number Division

 

수열을 여러 구역으로 쪼갤 수 있는데, 한 구역에 들어있는 숫자의 개수는 최소 2개여야한다.

각 구역을 모두 더한 값의 제곱을 모두 더해서 답을 구할 때, 답이 최소가 되는 값을 구하시오

 

일단 제곱했을때 값이 작아야하므로 무조건 한 구역에 들어가는 숫자의 개수는 2개여야한다.

이제 숫자 2개를 넣는 기준은 i번째로 작은 값과 i번째로 큰 값을 넣어주면 된다.

왜냐하면 제곱했을 때 값이 최대한 작아야하므로 숫자 두 개를 더한 값의 최대값이 가장 작아야하니까 제일 큰 값은 제일 작은 값이랑 더해야하고, 두번째로 큰 값은 두번째로 작은 값을 더해야하고,.. i번째로 큰 값은 i번째로 작은 값을 더하야 최대값이 최대한 작게 나올 수 있게 된다.

 

def main():
    n = int(input())
    a = sorted([*map(int,input().split())])
    ans = 0
    for i in range(n//2):
        ans += (a[i] + a[n-1-i])**2
    print(ans)

 

 

 

D. Lunar New Year and a Wander

 

주인공이 방문한 정점을 기록하며 이동 할 때, 이동하는 시간과 상관없이 무조건 사전순으로 제일 먼저오는 방문 순서를 구하는 문제이다.

 

일단 이건 사전순으로 제일 먼저오는 것을 구해야하니까 1번 노드부터 무조건 출발해야하고, 문제에 나와있듯이 숫자만 사전순으로 제일 먼저 나오게하면 되니까 방문한 노드를 몇번이고 방문해서 다른 노드로 이동해도 상관없다.

 

문제에서 요구한 그래프는 트리가 아닌데 트리로 그림을 그려서 예시를 들자면

 

 

 

이렇게 그림이 있을 때

1 2 3 4 5 6 7 이 답이 될 수 있는 것이다.

 

그래서 풀이 방법은 위 사진에서 1번부터 출발한다면

 

 

 

1을 방문했으니 2번 노드와 3번 노드를 갈 수 있으므로 heapq에 넣어준다.

heapq에 넣어두면 [ 2, 3 ]으로 정렬되어 있는데 2가 제일 작은 값이므로 2번 노드를 방문한다.

 

 

 

2번 노드를 방문했으면 이제 4번 노드와 6번 노드를 방문할 수 있는데, 이걸 heapq에 넣으면 [3, 4, 6]이 될 것인데 3이 제일 작은 값이므로 3번 노드를 방문한다.

 

 

 

3번 노드를 방문했으면 5번 노드와 7번 노드를 방문할 수 있게 된다. 이걸 heapq에 넣으면 [ 4, 5, 6, 7] 이 된다.

 

이걸 계속 반복하면 된다.

코드는 q는 deque(c++은 queue), eq는 heapq(c++은 우선순위 큐)를 이용하여 만들었다.

def main():
    n,m=map(int,input().split())
    adj = [[] for _ in range(n)]
    for i in range(m):
        u,v = map(int,input().split())
        u-=1;v-=1
        adj[u].append(v)
        adj[v].append(u)
    visit = [0]*n
    visit[0] = 1
    q=deque([0])
    eq = []
    ans = [1]
    while q:
        x = q.popleft()
        for nx in adj[x]:
            if not visit[nx]:
                heappush(eq,nx)
                visit[nx] = 1
        if len(eq):
            nx = heappop(eq)
            ans.append(nx+1)
            q.append(nx)
    print(*ans)