조합. 문제 풀이 팁

백준 15686

 

from itertools import combinations
import sys

N,M = map(int,sys.stdin.readline().split())

graph = []
for i in range(N):
    graph.append(list(map(int,sys.stdin.readline().split())))

house = []
chicken = []

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 :
            house.append([i,j])
        elif graph[i][j]==2:
            chicken.append([i,j])

answer = N*N*N
for comb in list(combinations(chicken, M)):
    totallen = 0
    for home in house:
        ptplen = N*N

        for x,y in comb :
            ptplen = min(ptplen,abs(home[0]-x)+abs(home[1]-y))

        totallen+=ptplen
    answer = min(answer,totallen)
            
        
print(answer)

 

백준 - 치킨 배달을 풀며

 

해당 풀이 과정은 

1. 여러개의 치킨중 M개의 조합을 구한다

2. 각 집에서, 해당 조합별로 몇의 최종 거리가 나오나 구한다

3. 집을 모두 모아서, 조합별로 몇의 최종 거리가 나오나 구한다.

4. 최소를 구한다 

 

가 된다.

 

하지만 바로 풀지 못했고, 그 이유는 조합을 찾아내는 함수를 몰랐기 때문이다.

1. 순열

from itertool import permutations로 선언한다. (순서에 상관있이, n개중 r개를 뽑는 수이다)
n! / n-k!

permutations(alist,2) -> alist가 [1,2,3,4]라면 -> ( (1,2), (2,1) .... ) 로 나온다.

 

2. 조합

from itertool import combinations

순서를 고려하지 않는, N! / N-K! K!이 된다.

combinations(alist,2) -> alist들의 원소들을 , 2개씩 묶는다. 

 

ALIST가 [ [1,2] .. ] 와 같은 2차원 배열이라면?

 

COMBINATIONS의 예시 .

2차원 배열 내부의 1차원 배열들을 원소처럼 (배열,배열....)의 형태로 묶음을 알 수 있다. 

 

주의할 점

LIST()로 COMBINATIONS이든, PERMUTATIONS든 묶어서 사용해야 한다.