.PNG)
50. 수열 추측하기
가장 윗줄에 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
<내 풀이>
- 어떻게 접근해야 하는지 모르겠다.. 1-2-3-4 이렇게 늘어나는 식이라서 a=1로 하고
else :
a+=1
for i in range(a):
DFS(x+1)이런 식으로 구현하려고 했는데 .. x==n-1이 되면 멈추고 체크해야한다는 걸 알겠는데 체크하는 걸 어떻게 f만을 가지고 할 수 있는지 알지 못했다===> 잘못된 접근 방법 ㅠㅠ
<풀이>
- 순열의 모든 가짓수를 체크하고 맞는 순열을 찾게 되면 break
- 근데 이거 너무 오래걸린다 => 파스칼 삼각형의 규칙을 이용하면 된다
=> 최종 숫자 (입력값이 세개일 땐 첫번째 숫자(1) + 두번째 숫자(2)+세번째 숫자(3)
/ 입력값이 네개일 땐 첫번째 숫자(1) + 두번째 숫자(3) + 두번째 숫자 (3) +네번째 숫자(1))
처럼 121- 1331 - 14641 - --- 그래서 이 리스트를 만들고
순열을 구하면 서로 곱해주다가 16나오면 정지하고 그것을 찾아내면 되는 것이다
#sum은 final숫자로 향해가는 애
def DFS(x,sum):
if sum==f and x==n:
for x in p:
print(x, end=' ')
sys.exit(0)
return
else :
for i in range(1,n+1) : #순열을 만들어내는 숫자들이 1,4까지이므로 1,n+1로
if ch[i]==0:
ch[i]=1
p[x]=i
DFS(x+1,sum+(b[x]*p[x]))
ch[i]=0
if __name__=='__main__' :
n, f = map(int, input().split())
p=[0]*n
ch=[0]*(n+1) #순열에서 중복 체크용
b =[1]*n #맨 앞, 맨 뒤는 1이니깐 1로 채워두면 편함
for i in range(1, n):
b[i]=(b[i-1]*(n-i))//i #콤비네이션 나타내기
DFS(0,0)
- 라이브러리를 이용한 순열 (수열 추측하기)
import itertools as it #순열이랑 조합을 바로 구해주는 함수
n,f = map(int, input().split())
b=[1]*n
for i in range(1,n) :
b[i]=b[i-1]*(n-1)/i
a=list(range(1,n+1))
for tmp in it.permutations(a) :
sum=0
for l,x in enumerate(tmp):
sum+=(x*b[L])
if sum==f:
for x in tmp:
print(x,end=' ')
break #답 발견하면 끝냐뷰려라(for구문)
#이렇게 하면 4팩 경우의 순열
#permutations(a,3) 이렇게 하면 4개 중 3개만 뽑아서<반성점>
- 설명을 들었는데도 어떻게 이항계수를 구해야 되는지 모르겠어서 막힌 점이 너무 아쉽다
- 순열이랑 거의 똑같이 진행되는 부분이 많은데도 헷갈리고 틀리는 부분이 많았다
- ch 설정하는 부분 (중복되는 숫자 오는 것 막기)
- else :
for i in range(1,n+1) (순열이 정해지는 부분은 1자리부터니깐, 이부분도 순열에 나와있음)
-
<배운 점>
-
파스칼의 삼각형 최종 수는 이항계수의 성질을 반영하고 있다 **
121 - 1331 - 14641 - 1 5 10 10 5 1 - ... -
콤비네이션 나타내기, 이항계수 구하기 :
b[i]=(b[i-1]*(n-i))//i -
라이브러리로 순열 구하기
import itertools as it #순열이랑 조합을 바로 구해주는 함수
n,f = map(int, input().split())
b=[1]*n
for i in range(1,n) :
b[i]=b[i-1]*(n-1)/i
a=list(range(1,n+1))
for tmp in it.permutations(a) :
print(tmp)
#이렇게 하면 4팩 경우의 순열
#permutations(a,3) 이렇게 하면 4개 중 3개만 뽑아서 순열
<2회독 내 풀이>
def DFS(x,s) :
if s==f and x==n:
for i in res:
if i!=0:
print(i, end=' ')
print()
sys.exit(0)
return
else :
for i in range(1,n+1) :
if ch[i]==0:
ch[i]=1
res[x]=i
DFS(x+1, s+res[i]*b[i])
ch[i]=0
if __name__=='__main__' :
n, f = map(int, input().split())
ch=[0]*(n+1)
res=[0]*(n+1)
b=[1]*(n+1)
for i in range(1,n) :
b[i]=(b[i-1]*(n-i))//i
DFS(0,0)
==> DFS 부른 후에 ch[i] 꼭 초기화해주기
==> 그리고 DFS(x+1, s+b[x] x res[x] 바로 하면 됨)
