- 파스칼의 삼각형의 원리를 떠올려보면 규칙을 발견할 수 있는 문제
- 이제 원리를 파악했으면 주어진 문제를 이를 기반으로 규칙을 찾아보자
- 코드 구현에 필요한 자료구조
- 원소의 개수가 주어졌을 때, 해당 숫자들의 조합을 만드는 코드를 구현해보자
- 전체 코드 구현
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
def DFS(level, sum):
if level==n and sum==target:
for x in n_ls:
print(x, end=" ")
sys.exit(0) # 사전순으로 print 하라고 하였는데 코드에서 이미 사전순으로 시작을 하므로
# 처음 발견하자마자 종료시키면 된다
else:
for i in range(1, n+1):
if check_ls[i]==0:
check_ls[i]=1
n_ls[level]=i
DFS(level+1, sum+(n_ls[level]*combination_ls[level]))
check_ls[i]=0
if __name__=='__main__':
n, target = map(int, input().split())
check_ls=[0]*(n+1)
n_ls=[0]*n
combination_ls = [1] * n # n열에 해당하는 파스칼 삼각형의 조합을 찾아라
for i in range(1, n): # 항상 양쪽 끝은 1이므로 1부터 시작했다
combination_ls[i] = combination_ls[i-1]*(n-i)//i
DFS(0, 0)
|
cs |
- 위에 처럼 DFS를 이용하여 코드 짜는 방식 말고, 파이썬 라이브러리를 이용할 수 있다
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import sys
import itertools as it #itertools 이라는 라이브러리를 이용해 조합을 만들 수 있다
if __name__=='__main__':
n, target = map(int, input().split())
combination_ls = [1] * n # n열에 해당하는 파스칼 삼각형의 조합을 찾아라
for i in range(1, n): # 항상 양쪽 끝은 1이므로 1부터 시작했다
combination_ls[i] = combination_ls[i - 1] * (n - i) // i
n_ls = list(range(1, n+1))
for tmp in it.permutations(n_ls, 4): # n_ls 의 조합을 구하는데 3개를 인수로 하는 조합을 구해라
res=0
for idx, comb in enumerate(combination_ls):
res+=comb*tmp[idx]
if res==target:
for x in tmp:
print(x, end=" ")
break
|
cs |
728x90