Codeforces Round #695 (Div. 2) A ~ C

codeforces.com/contest/1467

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

풀은 문제: A

못 풀은 문제: B, C, D, E

풀이만 보고 풀은 문제:

코드와 풀이 전부 본 문제: B, C 

 

 

난이도

A - 900

B - 1700

C - 1900

D - 2200

E - 2500

 

 

 

너무 피곤해서 잠깐만 자고 밤 11시에 일어나려다가 아침에 일어났는데 자길 잘한 듯

 

 

 

 

 

A. Wizard of Orz

 

숫자판 하나를 멈춘다면 1초뒤에 인접한 숫자판도 멈출 때, 최대값을 구하는 문제이다.

 

일단 첫번째 숫자판은 최대값이니 무조건 9이고, 두번째 숫자판은 8또는 0이 될 수 있는데 8이 최대값이므로 8이고, 세번째 숫자는 9 또는 7인데 9가 더 크므로 이것을 통해 두번째 숫자판이 8이 되었을 때 멈춰서 차례로 멈춰버리는게 답이다.

 

[9, 8, 9, 0, 1, 2, ...] 이므로 for문을 하든, 큐로 하든 아무거나 사용하면 된다.

 

def main():
    for _ in range(int(input())):
        n = int(input())
        if n == 1:print(9);continue
        ans = [0]*n;visit = [0]*n
        q=deque([[0,9]])
        ans[0] = 9; visit[0] =1
        ans[1]=8;visit[1]=1
        q.append([1,8])
        while q:
            x,t = q.popleft()
            nx,ny,nt=(x+1),(x-1),(t+1)%10
            for zx in [nx,ny]:
                if 0<= zx <= n-1 and not visit[zx]:
                    visit[zx] = 1
                    ans[zx] = nt
                    q.append([zx,nt])
        print(''.join(map(str,ans)))

 

 

 

 

B. Hills and Valleys

 

숫자를 딱 하나만 바꾸어 최소로 가질 수 있는 언덕과 계곡의 개수를 출력하면 되는 문제이다.

하나만 바꾸니까 일단 얻을 수 있는 최소값은 원래 언덕과 계곡의 개수에서 원래 언덕과 계곡의 개수에서 0~3을 빼면 답이라는 사실을 생각할 수 있다.

 

문제를 읽어보면 부등호가 < 또는 >이기 때문에 언덕과 계곡의 높이를 현재 위치의 오른쪽 높이 혹은 왼쪽 높이로 값을 맞추면 된다는 것을 알 수 있는데, 이게 오른쪽 높이에 맞추면 왼쪽에 언덕 또는 계곡이 생기는지 혹은 왼쪽 높이에 맞추면 오른쪽에 언덕 또는 계곡이 생기는지 확인해봐야하는게 이 문제의 제일 중요한 사항이다.

 

그래서 코드는 for문을 돌려서 계곡과 언덕의 개수와 좌표를 센 다음, 다시 그 좌표를 가지로 for문을 돌려서 계곡과 언덕을 오른쪽 높이에 맞추거나 혹은 왼쪽 높이에 맞춘다음 현재 위치, 왼쪽 위치, 오른쪽 위치에 계곡이나 언덕이 생기는지 확인하여 최소값을 찾으면 된다.

 

코드와 풀이는 103752387 를 참조하였다.

 

def main():
    def is_Valley_n_Hill(t):
        z = 0
        if 0 < t < n - 1:
            if a[t-1] < a[t] and a[t] > a[t+1]: z+=1
            if a[t-1] > a[t] and a[t] < a[t+1]: z+=1
        return z

    for _ in range(int(input())):
        n = int(input())
        a = [*map(int, input().split())]
        s = []
        for i in range(1, n - 1):
            if is_Valley_n_Hill(i): s.append(i)
        ans1 = len(s)
        ans2 = 0
        for x in s:
            k = [0, 0, 0] # [현재 언덕/계곡 개수, 왼쪽 높이에 맞췄을 때의 개수, 오른쪽 높이에 맞췄을 때의 개수]
            for nx in [x-1, x, x+1]: #현재 언덕/계곡의 개수
                if is_Valley_n_Hill(nx): k[0] += 1
            tmp = a[x]
            a[x] = a[x-1]
            for nx in [x-1, x, x+1]: #왼쪽 높이에 맞췄을 때의 개수
                if is_Valley_n_Hill(nx): k[1] += 1
            a[x] = a[x+1]
            for nx in [x-1, x, x+1]: #오른쪽 높이에 맞췄을 때의 개수
                if is_Valley_n_Hill(nx): k[2] += 1
            a[x] = tmp  #인접한 좌표가 있을 수 있으므로 원래 값으로 되돌려 놓음
            ans2 = min(ans2, k[1]-k[0], k[2]-k[0])
        print(ans1 + ans2)

 

 

 

C. Three Bags

constructive algorithm 태그가 붙은 문제들은 아이디어 찾아내는게 굉장히 중요한 문제인 것 같다.

이런 유형의 문제는 연습을 많이하면 풀 수 있는 문제인지 잘모르겠다.

 

문제 내용은 세 개의 가방이 있는데 이중에서 가방 두 개를 고르고, 각각 가방에서 숫자 하나를 골라서 숫자를 뺀 뒤 가방 하나에 다시 넣는 과정을 반복한다. 그러다보면 숫자가 하나만 남게 되는데 이때 그 숫자가 될 수 있는 최대값을 구하라는 문제이다.

 

문제를 읽어보면 숫자 a와 숫자 b를 골라서 a-b를 계산하면 음수가 되는 부분도 있고, 양수가 되는 부분이 있을텐데 어떻게 최대값을 만들 수 있을까에 대해 답을 생각해봐야한다.

곰곰히 생각해보면 어떤 수 하나를 선택하고 선택한 수에 해당 수를 제외한 모든 숫자를 전부 빼주면 제일 작은 수가 나올 수 있다는 생각을 할 수 있는데, 바로 이 아이디어가 문제의 핵심이 된다.

 

일단 선택해야하는 수는 세 개의 가방중에서 제일 작은 수인 것을 바로 알 수 있다. 왜냐면 제일 작은 수에 모든 수를 빼야 가장 작은 수가 나오기 때문이다.

그런데 가장 큰 값을 구하는 문제인데 가장 작은 수를 구하면 어떻게 처리하냐, 선택한 수에 있는 가방은 어떻게 처리하냐 이런 생각이 드는데 여기서 세 개의 가방중에 두번째로 가장 작은 수에 대해 생각해볼 수 있다.

 

상황 하나를 생각해보자

가방의 이름들은 각각 bag1, bag2, bag3이고, 각각 가방들을 모두 더한 값의 이름은 sum1, sum2, sum3이라고 가정하자

그리고 bag1~3중 가장 작은 수는 bag1의 a라는 수라고 하고, 두번째로 가장 작은 수는 bag2의 b라는 수라고 해보자

이제 그러면 bag1에 있는 a를 제외한 수들은 b에 전부 빼고, bag2에 있는 b를 제외한 수들은 a에 전부 뺀다는 생각을 할 수 있다.

이 과정을 거치면 각 가방에 들어있는 숫자를 모두 더한 값은

[ a - (sum2 - b), b - (sum1 - a), sum3 ] = [ a + b - sum2, a + b - sum1, sum3 ]

이 된다는 것을 알 수 있다. 그리고 가방에 들어있는 숫자의 개수는 [1개, 1개, x개]이다.

 

이제 bag3에 있는 수를 bag1이나 bag2에 있는 수에 빼야하는데, bag3에 있는 어떠한 수 y를 하나 남기고 아무곳에 나 숫자를 빼자

bag2에 숫자를 빼버린다고 하면 

[a + b - sum2, a + b - sum1 - (sum3 - y), y ] = [ a + b - sum2, a + b + y  - sum1 - sum3, y]

가 된다.

 

이제 bag1과 bag2를 bag3에 전부 빼버리면 sum1 + sum2 + sum3 - 2a - 2b라는 수만 남게 된다.

그런데 여기에 함정이 하나 있는데 만약 가방에 { 1, 3, 4 }, {10}, {20}처럼 a가 들어있는 가방의 모든 숫자 합이 b보다 크게되면 sum1 + sum2 + sum3 - 2a -2b = 38 - 1 - 20 = 17이지만 정답은 38 - 8로 30이다.

이걸 또 계산해보면 [ 4, 10 - 1, 20 - 3] => [ 1 + 4 - 10, 20 - 3] => [ 20 + 10 - 1 - 3 - 4 ]로 30이 답이다. 이건 bag3에 y를 남기는 과정처럼 구하면 된다.

 

그래서 최소값을 구하는 방법은 두 가지로 정리할 수 있다.

1) 두 개의 가방에서 각각의 최소값을 구해서 나머지 수를 처리하기

2) 한 개의 가방으로 나머지 가방에 있는 수를 처리하기

 

def main():
    x,y,z = map(int,input().split())
    X = [*map(int,input().split())]
    Y = [*map(int,input().split())]
    Z = [*map(int,input().split())]

    all_sum = sum(X) + sum(Y) + sum(Z)
    min_x, min_y, min_z = min(X), min(Y), min(Z)
    Min = min(min_x + min_y, min_x + min_z, min_y + min_z, sum(X), sum(Y), sum(Z))
    print(all_sum - 2 * Min)