백준(BOJ) 1060 좋은 수(Python)

문제 내용

 

그냥 시키는 대로 하면 되는 문제.

우선순위 큐가 태그에 있던데 그거 안 쓰고도 풀렸다.

집합 S에 속하는 수들을 정렬하고, 정렬된 리스트를 기준으로 i번째 수와 (i+1)번째 수의 차이를 구한 뒤 (i번째 수)+1과 함께 새로운 리스트에 저장한다. 이는 좋은 구간이 존재할 수 있는 구간이다.

이때 집합 S의 최솟값이 2라면 ans에 [0,1]을 추가하고, 그 외에도 구간의 길이가 1이라면 위에서 좋은 구간이 될 수 있는 리스트에 구간을 저장하지 않고 ans에 [0,구간에 해당하는 수]를 추가한다. 좋은 구간의 조건에 따르면 구간의 경계값은 같을 수 없기 때문에, 구간의 길이가 1이라면 좋은 구간의 개수가 0이라 뒤에서 탐색할 이유가 없기 때문이다.

그 후 집합 S에 속하는 수들에 대해서도 ans에 [0,1]을 추가한다. 이는 집합 S에 속하는 수들은 좋은 구간에 포함될 수 없기 때문이다.

그 후에는 좋은 구간이 존재할 수 있는, 위에서 저장한 모든 구간에 대해 최대 n개의 수를 고려해 ans에 저장한다. 만약 n개의 수를 저장하지 못하고 특정 구간을 모두 탐색했다면, 다음 구간으로 넘어간다.

좋은 구간의 개수는 현재 수를 그 구간의 n번째 수라고 하면, (구간의 길이)-1부터 (구간의 길이)-1-n까지의 합에 1부터 n-2까지의 합을 뺀 값이다.

그 후 ans를 좋은 구간의 개수를 1순위, 그에 해당하는 수를 2순위로 오름차순 정렬한다.

위 작업을 진행했음에도 불구하고 ans의 개수가 n보다 작다면 집합 S에서 가장 큰 수를 초과하는 수들을 오름차순으로 ans에 저장해 ans의 개수가n이 될 때까지 반복한다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

l=int(input())
S=list(map(int,input().split()))
S.sort()
n=int(input())
L=[]
ans=[]
q=0
if S[0]==2:
    ans.append([0,1])
elif S[0]>2:
    L.append([S[0]-1,1])
    q+=1
for i in range(l-1):
    if S[i+1]-S[i]-1==1:
        ans.append([0,S[i]+1])
    else:
        L.append([S[i+1]-S[i]-1,S[i]+1])
        q+=1
L.sort()
for i in S:
    ans.append([0,i])
for a,b in L:
    p=0
    q=a//2
    k=0
    while p<q and k<n:
        m=0
        if p>1:
            m=sum(range(p))
        ans.append([sum(range(a-1,a-p-2,-1))-m,b+p])
        ans.append([sum(range(a-1,a-p-2,-1))-m,b+a-1-p])
        k+=2
        p+=1
    if a%2:
        m=0
        if p>1:
            m=sum(range(p))
        ans.append([sum(range(a-1,a-p-2,-1))-m,b+p])
ans.sort()
p=len(ans)
k=1
while p<n:
    ans.append([0,S[l-1]+k])
    p+=1
    k+=1
for i in range(n):
    print(ans[i][1],end='')
    if i!=n-1:
        print(end=' ')

 

 

좋은 구간의 개수를 (구간의 길이)-1부터 (구간의 길이)-1-n까지의 합으로 계산해서 한참 헤맸다.

이렇게 해도 예제나 까다로운 반례들을 다 통과해서,,,

더 노력해야 할 것 같다.