[CLASS 3]백준 11723번, 17626번

11723번 : 집합

 

3가지 방법이 떠올랐다. 첫번째는 List로 구현하기, 두번째는 set을 사용해 간단하게 풀기, 3번째는 비트마스킹을 통해 풀기.. 근데 비트마스킹은 아직 나에게는 무리이고.. 첫번째와 두번쨰 방법으로 풀어보았다.

 

내 코드(List로 구현):

import sys
input = sys.stdin.readline

def bisect(S,number):
    left = 0
    right = len(S)-1
    while left <= right:
        mid = (left + right) // 2
        if S[mid] == number:
            return True
        elif S[mid] > number:
            right = mid - 1
        else:
            left = mid + 1
    
    return False

S = []
for _ in range(int(input())):
    cmd = input().split()
    
    if cmd[0] == 'add':
        if not bisect(S,int(cmd[1])):
            S.append(int(cmd[1]))
    elif cmd[0] == 'remove':
        if bisect(S,int(cmd[1])):
            S.remove(int(cmd[1]))
    elif cmd[0] == 'check':
        print(int(bisect(S,int(cmd[1]))))
    elif cmd[0] == 'toggle':
        if bisect(S,int(cmd[1])):
            S.remove(int(cmd[1]))
        else:
            S.append(int(cmd[1]))
    elif cmd[0] == 'all':
        S = [i for i in range(1,21)]
    elif cmd[0] == 'empty':
        S = []

    S.sort()

 

List를 이용하여 그냥 구현하였다. 속도는 4886ms..

 

내 코드(Set 사용):

import sys
input = sys.stdin.readline

S = set()
for _ in range(int(input())):
    cmd = input().split()
    
    if cmd[0] == 'add':
        S.add(int(cmd[1]))
    elif cmd[0] == 'remove':
        if (int(cmd[1]) in S):
            S.remove(int(cmd[1]))
    elif cmd[0] == 'check':
        print(int(int(cmd[1]) in S))
    elif cmd[0] == 'toggle':
        if (int(cmd[1]) in S):
            S.remove(int(cmd[1]))
        else:
            S.add(int(cmd[1]))
    elif cmd[0] == 'all':
        S = set([i for i in range(1,21)])
    elif cmd[0] == 'empty':
        S = set()

 

Set을 사용한다면 좀 편하긴 하다 속도는 6120ms..

 

문제에서 20개의 값만 준다고 했으니 이렇게 작성할수도 있다.

 

내 코드:

import sys
input = sys.stdin.readline

l = [False] * 21

for _ in range(int(input())):
    cmd = input().split()
    
    if cmd[0] == 'add' and not l[int(cmd[1])]:
        l[int(cmd[1])] = True
    elif cmd[0] == 'remove' and l[int(cmd[1])]:
        l[int(cmd[1])] = False
    elif cmd[0] == 'check':
        print(int(l[int(cmd[1])]))
    elif cmd[0] == 'toggle':
        l[int(cmd[1])] = not l[int(cmd[1])]
    elif cmd[0] == 'all':
        l = [True] * 21
    elif cmd[0] == 'empty':
        l = [False] * 21

 

보기는 좀 나아졌다.

 

17626번 : Four Squares

 

엄청 고민하고 시간을 많이 쓴 문제이다. 브루트포스법으로 풀면 그냥 범위만 잘 잡아주면 통과할 수 있는데, DP로 짠다면 실력이 부족해서 그런지 머리가 아프다... 그래도 어찌저찌 DP로 만들고 돌려봤는데.. Python으로 제출하면 시간초과가 뜬다.....

 

내 코드(브루트포스):

# 브루트포싱
n = int(input())

# 제곱수이면 그냥 1 출력
if (n**0.5) % 1 == 0:
    print(1)
    exit()

# 3개로 표현할수 있는지 확인하는 변수 t
t = False
for i in range(1,int((n//2)**0.5) + 1):
    for j in range(1,int((n - i**2)**0.5) + 1):
        if i**2 + j**2 == n:
            print(2)
            exit()
        elif (n - (i**2 + j**2))**0.5 % 1 == 0:
            t = True

# 3개의 제곱수로 표현할 수 없다면 증명에 의해 4
print(3 if t else 4)

 

문제에서 4가지 제곱수를 넘지 않는다는것이 증명되었으니 3가지인지만 검사하고 아니라면 4가지라고 생각하면 된다.

그리고 1가지는 그냥 n이 제곱수인 경우이니 제대로 검사해야되는것은 2가지일때와 3가지일때이다.

 

그리고 for문의 범위도 중요한데, 주어진 n을 반으로 나누고 제곱근을 취한 수까지만 검사하면 된다. 그 이후는 어짜피 순서만 바뀐 대칭이다. 만약 2중 for문 안에서 i^2 + j^2 이 n이 나온다면 2를 출력하고 종료하면 되고, 해당 수를 n에서 뺐을 때 제곱수라면 일단 3가지로 표현하는것이 가능하다고 기억하기위해 t변수에 True를 대입한뒤, 다른 i와 j의 검사를 마쳤을 때 (2가지로 표현하는것이 가능하여 중간에)종료되지 않았다면 t를 통해 3가지인지 4가지인지 판단하면 된다.

 

그러나 이것은 이미 증명을 알고있을 때의 코드이고, 만약 제대로 DP를 통해 작성하게 된다면 일단 생각해봐야 하는것은, 수들을 차례로 나열했을 때

 

1 = 1^2

2 = 1^2 + 1

3 = 1^2 + 2

4 = 2^2

5 = 2^2 + 1 or 1^2 + 4

 

...

 

k = (k이하의 제곱수) + (나머지)

 

로 표현할 수 있다.

 

그러면 k 라는 수를 표현하기위한 항의 개수중 하나는

 

1 + (나머지 수를 표현하기 위한 항의 개수중 최솟값)

 

이다. 이 값이 최소 1 최대 4 인 것이다. 그리고 이 값을 구하기 위해 k 이하의 제곱수 모두를 조사해 봐야 한다. (k이하의 제곱수를 구하기 위해 이진 탐색을 사용하였다. 해봤자 223개라 그닥 시간 차이가 날 것 같지는 않지만..)

그리고 이를 조사하는 과정에서 만약 한번이라도 2가 나왔다면 바로 for문을 나간다.

 

내 코드(DP,python 시간 초과):

from bisect import bisect_left
N = int(input())
squares = [i*i for i in range(1,int(N**0.5)+1)]
dp = [50001] * (N + 1)


for count in range(1,N+1):
    if count in squares:
        dp[count] = 1
    else:
        for i in range(bisect_left(squares,count)):
            dp[count] = min(dp[count],1+dp[count-squares[i]])
            if dp[count] == 2:
                break

print(dp[N])

이렇게 작성해서 제출했지만 아쉽게도 python에서는 시간 초과가 나고 pypy에서는 통과했다.

 

DP는 처음풀어봤는데 어질어질하다 ㅠㅠ 노력이 더욱 필요할 것 같다.