.PNG)
51. 조합 구하기
이 문제를 베이스로 해서 응용되는 문제가 많이 나온다, 꼭 열심히 암기하고 외우자
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그
램을 작성하세요.
▣ 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.
▣ 출력설명
첫 번째 줄에 결과를 출력합니다. 맨 마지막 총 경우의 수를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다.
▣ 입력예제 1
4 2
▣ 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
6
<내 풀이>
- 엉망진창인 풀이다. 일단 1,2 랑 2,1 겹치면 2,1없애야 하는 조건 안 만들었고
일단 그런거 상관없이 쭉 나오게 하고 싶었는데 결과가
1 2
1 3
1 4
3
이렇게 1로 시작되는 애들만 나오고 끝난다. 원인이 무엇일까?
def DFS(x):
global ch
global cnt
if x==m:
for j in range(m) :
print(p[j], end=' ')
print()
cnt+=1
else :
for i in range(1,n+1):
if ch[i]==0 :
ch[i]=1
p[x]=i
DFS(x+1)
ch[i]=[0] #ㅋ..나중에 뵈깐 여기를 이렇게 했었다ㅠㅠㅠㅠㅠ
p[x]=0
if __name__=='__main__' :
n, m = map(int, input().split())
cnt=0
ch=[0]*(n+1)
p=[0]*n
DFS(0)
print(cnt)
(2) 1,2 = 2,1 이 같다는 조건을 세우기 전..
def DFS(x):
global ch
global cnt
if x==m:
for j in range(m) :
print(p[j], end=' ')
print()
cnt+=1
else :
for i in range(1,n+1):
if ch[i]==0:
ch[i]=1
p[x]=i
DFS(x+1)
ch[i]=0
if __name__=='__main__' :
n, m = map(int, input().split())
cnt=0
ch=[0]*(n+1)
p=[0]*n
DFS(0)
print(cnt)
하면
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
12
로 출력된다. 이제 동일한 것으로 취급 되는 애들을 지워주기만 하면 된다
=> 비교할 리스트를 만들어주면 되나?
==>여기서 막혔다 ㅠㅠ
====>결국 강의에서 설명만 듣고 구현해본 결과
def DFS(x,s):
global ch
global cnt
if x==m:
for j in range(m) :
print(res[j], end=' ')
print()
cnt+=1
else :
for i in range(s,n+1):
res[x]=i
DFS(x+1,s+i) #이 부분이 틀렸다.. s가 i만큼 증가하는게 아님아님!!!!
if __name__=='__main__' :
n, m = map(int, input().split())
res=[0]*m
cnt=0
DFS(0,1) #처음에 s는 1에서 시작
print(cnt)
<풀이>
- 새로운 상태트리로 만들어주면 된다
D(0,1) => D(1,2) , D(1,3), D(1,4) =>
def DFS(x,s):
global ch
global cnt
if x==m:
for j in range(m) :
print(res[j], end=' ')
print()
cnt+=1
else :
for i in range(s,n+1):
res[x]=i #가지를 뻗는 것은 i로부터..D(0,1)에서 1,2,3,4 가지가 뻗어지고
#(for i in range(s,n+1)=> 각각 D(1,2) D(1,3) D(1,4) D(1,5) 로 넘어간다.
# 따라서 넘어갈 때 i+1로 넘어가면 되는 것이다
DFS(x+1,i+1) #레벨은 1 증가하고, s는 i+1 로 변신
if __name__=='__main__' :
n, m = map(int, input().split())
res=[0]*m
cnt=0
DFS(0,1)
print(cnt)
<반성점>
- 많이 응용된다고 하니 지금까지 배운 트리들을 잘 복습하고 활용할 수 있게 익숙해지는 연습을 해야곘다
- 설명을 듣고서도 헷갈렸다. 처음에는 s+i인줄 알았다 (사실 이것도 대충 찍어서..)
앞으로는 생각하고 풀어야한다 - 너무 어려운 개념이었다
<배운 점>
-
조합 :
D(0,1)에서 시작해서 범위를 s로부터 가지가 뻗을 수 있게 잡아주기
D(0,1) 다음에 D(x+1) 되면, D(1,2)-1 D(1,3)-2 D(1,4)-3 D(1,5)-4 근데 S가 4 넘으니깐 얘는 중지, 그 다음에 첫번째 애로부터는 D(2,3)-2 D(2,4)-3 / D(2,4) -
else :
for i in range(s,n):
res[x]=a[i]
DFS(x+1,i+1) ***i+1이다 i를 기준으로 하나씩 커지는 것
if name=='main' :
n, k = map(int, input().split())
a=list(map(int, input().split()))
m=int(input())
res=[0]*(k+1)
DFS(0,0)
===> i+1이다!
<두번째 내 풀이>
def DFS(x,s) :
if x==m :
for i in res :
print(i, end=' ')
print()
return
else :
for i in range(s,n+1) :
res[x]=i
DFS(x+1, i+1)
if __name__=='__main__' :
n, m = map(int, input().split())
res=[0]*m
DFS(0,1)
