[알고리듬] 수열 추측하기
수열 추측하기
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼
의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3
1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
3 1 2 4
4 3 6
7 9
16
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하
시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
▣ 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의
미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다.
▣ 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다. 답이 존재
하지 않는 경우는 입력으로 주어지지 않는다.
▣ 입력예제 1
4 16
▣ 출력예제 1
3 1 2 4
풀이
- 결과 값을 모두 알기 위해 순열을 사용했습니다.
- 파스칼의 삼각형으로 이항계수를 사용하면 좋습니다.
처음 푼 풀이
def solution(a):
while len(a) > 1:
b = list()
for i in range(len(a) - 1):
b.append(a[i] + a[i + 1])
a = b.copy()
return a[0]
n, f = map(int, input().split())
lst = [i for i in range(1, n + 1)]
for item in list(permutations(lst, n)):
res = solution(list(item), b)
if res == f:
item = list(map(str, item))
print(" ".join(item))
break
- 이 부분의 문제가 뭐냐면, solution에서의 시간 복잡도가 너무 많이 들어갑니다.
3 1 2 4
4 3 6
7 9
16
- 위의 삼각형을 모두 더하는 과정이 solution인데 리스트를 순열을 사용하는 것 자체도 시간복잡도가 O(n!)이기 때문에 전체적인 시간복잡도가 많이 들어갑니다.
- 여기서 해결책은 바로 이항 계수입니다.
- 위와 같은 다항식의 계수들로 표현되는 것이 이항 계수입니다.
3 1 2 4
4 3 6
7 9
16
- 여기 파스칼의 삼각형에서 맨 마지막 줄의 16은 3+1+1+1+2+2+2+4입니다.
즉, 3이 한 번, 1이 세 번, 2가 세 번, 4이 한 번 더해지는 구조입니다.
다시 한번 이항 계수로 써보면 3C0 + 3C1 + 3C2 + 3C3입니다.
- 위와 같이 solution을 작성하는 것보다 아래와 같이 이항계수를 사용해서 하는 것이 좋습니다.
def solution(a, mul):
for i in range(n):
a[i] *= mul[i]
return sum(a)
n, f = map(int, input().split())
lst = [i for i in range(1, n + 1)]
b = [1] * n
# 이항계수 구하기
for i in range(1, n - 1):
b[i] = b[i-1] * (n - i) // i
for item in list(permutations(lst, n)):
res = solution(list(item), b)
if res == f:
item = list(map(str, item))
print(" ".join(item))
break
Author And Source
이 문제에 관하여([알고리듬] 수열 추측하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sparkbosing/알고리듬-수열-추측하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)