Codeforces Round #693 (Div. 3) 풀이

A번 풀이

 

이문제는 w*h크기의 종이를 2로 나누어 떨어질때까지 나누면서 개수가 n개이상이 나올수있는지 판단하는 문제이다. 처음에 이문제를 식으로 할려다가 계속 틀려서 그냥 반복문으로 해주었더니 맞았다;;

a=int(input())
for i in range(a):
    b,c,d=map(int,input().split())
    s=1
    while 1:
        if b%2!=0:break
        s*=2
        b//=2
    while 1:
        if c%2!=0:break
        s*=2
        c//=2
    if d>s:
        print("NO")
    else:
        print("YES")

 

B번 풀이

 

이문제는 입력으로 주어진 배열들의 값을 똑같게 둘로 나눠야되는데 이때 값을 나누면 안된다. 처음에 개수로 판단하는 코드를 짰다가 2번째에서 틀렸는데 생각해보니 만약 1 1 1 1 1 1 2 2 2

이렇게 있다면 한쪽은 2가 2개에 1이 2개 한쪽은 2가 1개에 1이 4개로 될수있다는것을 알아서

a=int(input())
for i in range(a):
    t=int(input())
    l=list(map(int,input().split()))
    y=[0,0]
    for g in range(t):y[l[g]-1]+=1
    if y[0]%2==0 and y[1]%2==0:
        print("YES")
    else:
        print("NO")
        

(틀린코드)

2의 개수를 구해주고 반으로 나눴을때 몇개나 차이나는지 확인후 1의 개수에서 2의 개수 차만큼 빼주고 2로 나눴을때 0이면 yes 아니면 no로 나오게 해줬고 만약 1이 2가 필요한 개수보다 적을경우 No를 출력하게 해줘서 맞았다.

 

a=int(input())
for i in range(a):
    t=int(input())
    l=list(map(int,input().split()))
    y=[0,0]
    for g in range(t):y[l[g]-1]+=1
    p=(((y[1]+1)//2-y[1]//2)*2)
    if y[0]<p:print("NO")
    elif (y[0]-p)%2==0:
        print("YES")
    else:
        print("NO")

 

C번 풀이

C번은 못풀었는데 푼분의 말로는 dp이고 뒤에서 부터 비교하면서 하면 되는 생각보다 간단한 풀이였다

 

D번 풀이

 

D번은 번가라가면서 자신이 가지고 갈수있는 최대값과 상대방의 최대값중 자신이 가지고 갈수있는 최대값이 더 큰경우 가지고 가지만 상대방의 최대값이 더 큰 경우 그 값을 가져가는 방식으로 했는데 처음에 코드를 짰다가 시간초과가 나서

 

import math
a=int(input())
for i in range(a):
    t=int(input())
    l=list(map(int,input().split()))
    y=[0,0]
    r=0
    while l!=[]:
        r+=1
        u=[-1,0,-1,0]
        for i in range(len(l)):
            if l[i]%2==0:
                if l[i]>u[0]:
                    u[0]=l[i]
                    u[1]=i
            else:
                if l[i]>u[2]:
                    u[2]=l[i]
                    u[3]=i
        #print("#!",u)
        if r%2!=0:
            if u[0]>u[2]:
                y[0]+=u[0]
                l.pop(u[1])
            else:
                l.pop(u[3])
        else:
            if u[2]>u[0]:
                y[1]+=u[2]
                l.pop(u[3])
            else:
                l.pop(u[1])
    #print("%",y)
    if y[1]>y[0]:
        print("Bob")
    elif y[1]<y[0]:
        print("Alice")
    else:
        print("Tie")

(시간초과 코드)

 

생각을 해보다가 배열을 짝,홀로 나눈다음 정렬하고 짝위치값,홀위치값을 변경하면서 비교해주니 맞았다.

import sys
input=sys.stdin.readline
a=int(input())
for i in range(a):
    t=int(input())
    l=list(map(int,input().split()))
    y=[[-1],[-1]]
    for i in range(t):y[l[i]%2].append(l[i])
    y[0].sort()
    y[1].sort()
    le=[0,0]
    left=len(y[0])-1
    right=len(y[1])-1
    for i in range(t):
        if i%2==0:
            if y[0][left]>y[1][right]:
                le[0]+=y[0][left]
                if left-1>-1:left-=1
            else:
                if right-1>-1:right-=1
        else:
            if y[0][left]<y[1][right]:
                le[1]+=y[1][right]
                if right-1>-1:right-=1
            else:
                if left-1>-1:left-=1
    if le[1]>le[0]:
        print("Bob")
    elif le[1]<le[0]:
        print("Alice")
    else:
        print("Tie")

 

나머지 문제들은 문제 풀이랑 설명을 못봐서 못쓰지만 처음으로 3솔해서 기분이 좋다.