1부터 n까지 각각 1번씩 정확히 k개의 정수만 사용해서 합을 s로 만드는 그리디 알고리즘

19177번: Klothes (acmicpc.net)

 

1부터 n까지의 자연수 중에서 각각 1번씩만 사용하고, 정확히 k개의 정수만 사용해서 합을 s로 만드는 방법을 찾는 문제

 

n이 40000까지이고 테스트케이스가 8000개이다 보니 단순한 방법보다는 O(N)정도에 하나는 해결해야

 

 

만약 s가 가능한 범위를 벗어난다면 일단 만들수가 없다.

 

s의 최솟값은 1부터 k까지 합

 

s의 최댓값은 n-k+1,n-k+2,...,n까지의 합

 

만약 s가 (1부터 k까지 합) <= s <= (n-k+1,...,n까지 합)이 아니라면 어떻게 해도 만들수가 없다.

 

 

반대로 이 범위 안이라면 확실하게 만들 수 있다는 것이 보장된다.

 

(1부터 k까지의 합) = a

 

(n-k+1,...,n까지의 합) = b라고 할 때, a,a+1,a+2,..,b-1,b까지의 모든 정수는 반드시 만들 수 있다.

 

어떤 정수는 안되는게 있을수도 있는거 아니야?

 

그냥 1부터 k까지 골라서 만들었다고 하자. 이 합이 a이다.

 

그 다음 a+1은 어떻게 가능할까?

 

k 대신에 k+1을 고르면 a+1을 만들 수 있다.

 

그 다음 k+2를 고르면 a+2를 만들 수 있다.

 

....

 

이런식으로 현재 고른 수 집합 내에 있는 어떤 수보다 1 더 큰 값을 고르면 반드시 이전 수보다 1 더 큰 값을 만들 수 있다.

 

 

 

이제 현재 k개의 정수를 사용할 수 있다고 할때, 1부터 n중 사용할 수 있는 가장 큰 값은?

 

최솟값 1~k-1만을 사용했을 때, s - (1부터 k-1까지의 합)을 사용하면 된다.

 

 

근데 문제는 1부터 n까지만 사용해서 만들어야하는데

 

s - (1부터 k-1까지의 합)이 n을 넘어갈 수 있다는 점이다.

 

 

예를 들어 1,2,3,4,5,6,7,8에서 4개의 정수만 사용해서 17을 만든다고 해보자.

 

4개의 정수만 사용했을 때 최솟값은 1+2+3+4 = 10, 최댓값은 5+6+7+8 = 26

 

이 사이에 있는 17은 반드시 4개의 정수로 만들 수 있다.

 

 

먼저 1부터 3까지 사용했다고 가정한다면 1+2+3 = 6이고 17-6 = 11을 사용해야 나머지를 채울 수 있다.

 

그런데 11은 8을 넘어가서 사용할 수 없다.

 

그래서 어쩔수 없이 8을 먼저 채우고 17 - 8 = 9를 나머지 3개로 채운다.

 

 

동일한 방법으로 1부터 2까지 1+2 = 3을 사용했다고 하자. 

 

그러면 9 - 3 = 6을 사용하면 된다. 여기서 6은 아직 사용하지도 않았고, 8이내이므로 사용할 수 있다.

 

 

그런 다음에 계속 진행해야할까?

 

그럴 필요 없이 나머지 2개의 수는 6을 사용한 순간 이미 1,2로 정해져버렸다.

 

-------------------------------------------------------------------------------------------------------------------------------

 

정리하면 주어진 s가 가능한 합 범위 내에 존재하는지 체크

 

1) (1부터 k까지 합) <= s <= (n-k+1,...,n까지 합) 이면 만들 수 있고 그렇지 않으면 만들 수 없다

 

2) 만들 수 있는 경우라면, 

 

1부터 k-1까지 사용했다고 가정할때 가장 큰 값은 s - (1부터 k-1까지 합)과 n중 하나이다.

 

만약 s - (1부터 k-1까지 합) > n이라면 n을 사용하고, k를 1 감소하고 s에서 n 감소시키고, n은 쓸 수 없으므로 n을 1 감소시킨다.

 

만약 s - (1부터 k-1까지 합) <= n이라면 s - (1부터 k-1까지 합)을 사용하고, 나머지는 1,2,3,..,k-1로 채우면 끝이다.

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    n,s,k = map(int,stdin.readline().split())
    
    #1부터 k까지 합 = (k*(k+1)//2)
    #n-k+1,n-k+2,...,n까지 합 = (1부터 n까지 합) - (1부터 n-k까지 합)
    #만약 s가 (k*(k+1)//2)보다 작거나, (n*(n+1)//2) - ((n-k)*(n-k+1)//2)보다 크면 불가능하다.
    if s < (k*(k+1)//2) or s > (n*(n+1)//2) - ((n-k)*(n-k+1)//2):
        
        print('NO')
    
    else: #범위 내라면 확실하게 만들 수 있다.

        answer = ['0']*n

        while k > 0:
            
            #가장 작은 가격 1~k-1까지 선택했다고 한다면, 나머지 하나는
            a = s - ((k-1)*k//2)
            
            #a가 n보다 큰 경우가 있을 수 있다.
            if n < a:

                #그런 경우에는 n을 사용하고
                answer[n-1] = '1'

                s -= n #n을 썼으니까
                k -= 1 #1개 썼으니까
                n -= 1 #n을 썼으니까 n은 사용 불가하고 1 감소시켜서 제한을 갱신
            
            else:
                
                #a가 n보다 작다면 a를 선택하고
                answer[a-1] = '1'
                
                #그 다음은 1부터 k-1까지로 채우면 된다.
                for i in range(1,k):
                    
                    answer[i-1] = '1'
                
                break

        print('YES')
        print(''.join(answer))