[백준] 15686 치킨 배달

---

도시에 존재하는 치킨 집을 M개 만큼 남기는 경우의 수 중 최소 치킨 거리를 구하는 문제이다. 

 

모든 치킨 집 중 M개를 뽑는 조합을 구하면 쉽게 답이 도출된다.

 

다만 나는 시간 초과로 인해 조금 헤매었다. 그 이유는 지금까지 조합과 순열에 대한 차이를 인지하면서 알고리즘을 작성하지 않았던기 때문이다. 

 

조합은 순서를 무시하기 때문에 [1, 2]와 [2, 1] 동일하다. 즉 [(1, 2), (3, 2)]에 위치한 치킨 집을 폐업 시키는 경우와 [(3, 2), (1, 2)]에 위치한 치킨 집을 폐업 시키는 경우가 동일한 것이다. 이러한 문제에 순열 알고리즘을 사용하였으니 시간초과가 발생하는 것이 당연한 것이었다.

순열과 조합 알고리즘의 간단한 예시는 아래와 같다.

# 순열

li = [1, 2, 3, 4, 5, 6]
M = 4

def dfs(result):
    if len(result) == M:
        return
    print(result)
    for l in li:
        dfs(result + [l])
dfs([])

# 조합

li = [1, 2, 3, 4, 5, 6]
M = 4

def dfs(idx, result):
    if idx >= len(li): return
    if len(result) == M:
        return
    print(result)
    dfs(idx+1, result + [li[idx]])
    dfs(idx+1, result)

dfs(0, [])

 

Python