조합 구하기

1부터 N까지 번호가 적힌 구슬이 있습니다.

이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.

 

▣ 입력설명

첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다.

 

▣ 출력설명

첫 번째 줄에 결과를 출력합니다.

맨 마지막 총 경우의 수를 출력합니다.

출력순서는 사전순으로 오름차순으로 출력합니다.

 

▣ 입력예제

4 2

 

▣ 출력예제

1 2

1 3

1 4

2 3

2 4

3 4

6

 

---

내가 쓴 코드

def DFS(v):
    global cnt
    if v == (M+1):
        for i in range(1,M+1):
            print(result[i], end=' ')
        print()
        cnt += 1
    else:
        for j in range(result[v-1]+1, N+1):
            result[v] = j
            DFS(v+1)

if __name__ == "__main__":
    N,M = map(int, input().split())
    cnt = 0
    result = [0]*(M+1)
    DFS(1)
    print(cnt)

 

모범답안

def DFS(L, s):
    global cnt
    if L == m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt += 1
    else:
        for i in range(s, n+1):
            res[L] = i
            DFS(L+1, i+1)

if __name__=="__main__":
    n,m = map(int, input().split())
    res = [0]*m
    cnt = 0
    DFS(0,1)
    print(cnt)

 

느낀점

1. 우선 순서가 다르지만 조합이 중복되는 경우를 제외하는 것이 이번 문제의 핵심인듯했다.
나는 그걸 result에 직전에 담은 값보다 1 큰 숫자부터 반복문을 돌리면서 했는데..
그렇게 안하고 그냥 직전에 넣은 값+1을 아예 매개변수로 담아서 다음 레벨의 DFS문을 돌리는 방법이 있었다!
흠 역시 모범답안은 똑똑하군 
하지만 나도 포인트는 잘 잡았으니 아주 잘했다. 다시 풀어보쟝

2. 매개변수를 꼭 하나만 넣어야 한다는 생각을 버려라
처음에는 잔뜩 넣더니 왜 요샌 하나만 넣는거지? 
항상 하나의 생각에 갇히지 말고 여러 가능성을 바라보쟈~

 

---

다시 풀어보기

def DFS(v, start):
    global cnt
    if v == M:
        for x in res:
            print(x, end=' ')
        print()
        cnt += 1
    else:
        for i in range(start, N+1):
            res[v] = i
            DFS(v+1, i+1)

if __name__=="__main__":
    N, M = map(int, input().split())
    cnt = 0
    res = [0]*M
    DFS(0,1)
    print(cnt)