문제 바로가기
이 문제는 어떤 수열의 총 길이와 총 합이 주어진다.
예를들어 n = 2 m = 3 이면 길이가 2짜리 수열이며 그 수열의 총 합이 3이다
[1,2] 그 예가 될 수 있다.
그리고 B 수열이 주어지는데 B수열은 위에 있는 A 수열의 모든 부분합의 갯수이다 위에 예시로 해보면
n =2 , m = 3 이고
B = 1 1 1 1 이면
빈거, 1, 2, 1+2 이렇게 해서 4개가 나오는데 이것들의 각각의 합과 갯수로 분류하면
1 1 1 1 이렇게 나오는거다
문제에서는 가장 작은 수열을 구하라고 하였다. 즉 가장 작은 수부터 찾아가면 되는데 시작값인 0 은 빼준다 모든수에 들어가기 때문에
그러면 일단 시작값인 0 은 무조건 들어가니깐 빼주고
처음 들어오는 B 배열을 Counter 함수로 그 숫자가 될 수 있는 갯수로 나타낸다
합해서 1 될 수 있는 수는 1개
합해서 2 될 수 있는 수는 1개
이런식으로
B_counter = defaultdict(int)
for idx, i in enumerate(B[1::], start=1):
B_counter[idx] = i
B_counter = Counter(B_counter)
길이가 n이니 n만큼 수열을 돌면서 배열을 찾아주면 되는데
Counter에서 작은 수부터 찾아 1개라도 있으면 그것을 배열에 넣어주고
Counter에서 찾은 수는 1개를 빼누다
for _ in range(n):
for a in range(1, m + 1):
if B_counter[a] > 0:
break
A.append(a)
B_counter[a] -= 1
여기서 제일 중요한 a 가 들어간 합 들을 모두 빼줘야한다
예를들어 1은 2를 만들수있고 3도,4도 등등 가능하다
1. 다음 과정을 인 에 대하여 값이 증가하는 순서대로 수행한다
이라면 를 감소시킵니다. 를 포함하지않은 부분 수열들 중 합이 인 부분 수열의 갯수가 개이고
3. 이 말은 즉, 를 포함하면서 합이 인 부분 수열의 갯수가 개라는것을 의미한다. 그래서 를 감소시킵니다.
for i in range(a, m + 1):
if B_counter[i] > 0:
B_counter[i + a] -= B_counter[i]
그리고 출력해준다.
전체코드
import sys
from collections import Counter, defaultdict
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int, input().split(" "))
arr = list(map(int, sys.stdin.read().split()))
def restore_sequence(n, m, B):
A = []
B_counter = defaultdict(int)
for idx, i in enumerate(B[1::], start=1):
B_counter[idx] = i
B_counter = Counter(B_counter)
for _ in range(n):
# Step 1: B 배열에서 최솟값 찾기
for a in range(1, m + 1):
if B_counter[a] > 0:
break
# Step 2: 최솟값 a를 A에 추가하고, B 배열 업데이트
A.append(a)
B_counter[a] -= 1
for i in range(a, m + 1):
if B_counter[i] > 0:
B_counter[i + a] -= B_counter[i]
return A
A = restore_sequence(n, m, arr)
print(' '.join(map(str, A)))
댓글