[Python] 조합 문제 풀이 정리(2)

https://www.acmicpc.net/problem/6603

• python 라이브러리 combinations을 사용하면 쉽게 풀 수 있지만...직접 구현해서 풀자

# 정답 풀이
import sys
input = sys.stdin.readline

def dfs(depth, idx):
    if depth == 6:
        print(*out)
        return

    for i in range(idx, k):
        out.append(S[i])
        dfs(depth + 1, i + 1)
        out.pop()

while True:
    array = list(map(int, input().split()))
    k = array[0]
    S = array[1:]
    out = []
    dfs(0, 0)
    if k == 0:
        exit()
    print()

• DFS를 이용한다. depth는 로또 번호 길이로 6이 되면 return하고, idx로 번호를 순회한다.

 

https://www.acmicpc.net/problem/9375

# 정답 풀이
import sys
import math
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    clothes = {}
    for _ in range(n):
        a, b = map(str, input().split())
        if b in clothes:
            clothes[b] += 1
        else:
            clothes[b] = 1
    ans = 1
    for i in clothes:
        ans *= (clothes[i]+1)
    print(ans-1)

• 종류당 옷의 개수 +1을 곱하고, 모두 안입는 경우를 제외한 ans-1을 해준다.
• 모든 옷 종류 + 옷을 선택하지 않는 경우의 수(1)

 

https://www.acmicpc.net/problem/2407

import sys
import math
input = sys.stdin.readline

c,m=map(int, input().split())

print(math.factorial(c)//(math.factorial(m)*math.factorial(c-m)))

 

 

https://www.acmicpc.net/problem/10972

# 정답 풀이
n = int(input())
data = list(map(int, input().split()))

for i in range(n-1, 0, -1): # 맨 뒤 값부터 시작
    if data[i-1] < data[i]:
        for j in range(n-1, 0, -1): # 다시 맨 뒤 값부터 큰 값찾기
            if data[i-1] < data[j]:
                data[i-1], data[j] = data[j], data[i-1] # 둘 값을 swap
                data = data[:i] + sorted(data[i:])
                for i in data:
                    print(i, end=' ')
                exit()
print(-1)

• 모든 순열을 구하는 방식은 시간초과가 난다.
• 다음 순열을 찾는 방법은 주어진 순열(data)의 맨 뒤에서부터 탐색하며 앞 숫자가 뒷 숫자보다 감소할때 해당 숫자를 뒤집으면 된다. 뒤집은 뒤 다음 숫자들은 정렬한다.

 

https://www.acmicpc.net/problem/10973

n = int(input())
data = list(map(int, input().split()))

for i in range(n-1, 0, -1): # 맨 뒤 값부터 시작
    if data[i-1] > data[i]:
        for j in range(n-1, 0, -1): # 다시 맨 뒤 값부터 작은 값찾기
            if data[i-1] > data[j]:
                data[i-1], data[j] = data[j], data[i-1] # 둘 값을 swap
                data = data[:i] + sorted(data[i:], reverse=True)
                for i in data:
                    print(i, end=' ')
                exit()
print(-1)

• 이전 문제랑 완전 반대로~ 뒤 숫자를 정렬할 때 reverse하는 것을 잊지 말자.

 

---

# 회고

 

조합은 너무 어렵다ㅜㅜㅜㅜ

식을 찾는 것 자체가 뭔가...생각해내는게 안된다. 물리 푸는 기분이야....이것도 풀다보면 좀 보일려나..?

일단 좀 더 연습을 하고 와야할 것 같다!