백준 17528 문제 -재귀호출을 이용하여-

해당 알고리즘 문제는 BOJ(BAEKJOON ONLINE JUDGE)의 17528번: Two Machines (acmicpc.net)를 참고 하였으며, 해당 글은 이용 규칙 (acmicpc.net)을 준수하였음을 알려드립니다.

 

---

Two Machines 문제를 풀기 위해서, 다음과 같이 아이디어를 생각했다.

 

i = 1일때, 리스트 a와 b에 요소 하나 씩 입력받아 최솟값을 구한다.

 

 예를들어, \(a_1\)=[2], \(b_1\)=[3] 일때, A Machine으로 작업을 했다면 t = 2 B Machine으로 작업을 했다면 t = 3 이 되고 둘 중 최솟값인 t=2를 출력하게 된다.

 

i = 2일때, 리스트 a와 b에 요소 두개 씩 입력받아 최솟값을 구한다.

 

 예를들어 \(a_1\)=[2,5], \(b_1\)=[3,3] 일때

• A Machine으로만 작업을 했다면 \(t_1\) = 2, \(t_2\) = 5 \(\Rightarrow\) 7시간
• B Machine으로만 작업을 했다면 \(t_1\) = 3, \(t_2\) = 3 \(\Rightarrow\) 6시간
• A Machine\((a_1)\)과 B Machine\((b_2)\)으로 하나씩 작업을 했다면 \(t_1\) = 2, \(t_2\) = 3 \(\Rightarrow\) 3시간
• B Machine\((b_1)\)과 A Machine\((a_2)\)으로 하나씩 작업을 했다면 \(t_1\) = 3, \(t_2\) = 5 \(\Rightarrow\) 5시간

i = 1, i = 2를 각 각 그림으로 표현하면,

i = 1 일때의 알고리즘

 

i = 2 일때의 알고리즘

 

마찬가지로 i = 3 일때를 그림으로 표현하면 다음과 같다.

 

 

그림에서 확인 할 수 있듯이 알고리즘의 순서를 표현하면 다음과 같다.

 

 

1. a와 b로 만들 수 있는 조합을 나열한다. 조합의 개수는 \(2^i)개가 된다.

 

2. a는 a끼리 더하고 b는 b끼리 각각 더해주고 난후 Max(\(\sum a_i , \sum b_i\)) 값을 구한다.(모든 일이 끝나는 t를 구하기 위해서)

 

3. 각각의 Max값을 비교하여 그 중 가장 작은 값이 출력 값이 된다.

 

먼저 1을 코딩하기 위해서 입력받은 list(\(a_i\),\(b_i\))로 만들수 있는 조합을 나열해야한다. 대표적으로 다음 두가지 방법을 이용한다.

 

1) itertools 라이브러리를 이용하여 조합 구하기.

python에서는 순열,조합을 쉽게해주는 itertools 라이브러리가 있다. 순열을 할 때는 permutations를 import하고 조합을 할 때는 combinations를 import한다.

 

예를들어 list [1,2,3,4]중에 중복을 허용하지 않고 2개를 뽑는다고 했을때 다음과 같이 나타낸다.

 

a=[1,2,3,4]
 
from itertools import combinations
for i in combinations(a, 2):
    print(i, end=" ")
 

2) 재귀호출로 직접 알고리즘 작성

 재귀호출은 내가 만든 함수에 다시 그 함수를 넣어서 종료조건을 만날때까지, 실행하는 경우를 이야기한다.

 

예를들어 Hellow!를 n번 추출한다고 해보자.

def hello(count):
    if count == 0:
        return
    print('Hello!',count)
 
    count -= 1
    hello(count)
 
hello(5)
 

 

 알고리즘 코딩 테스트는 라이브러리를 쓰지 못하기 때문에 조합과정을 직접 코딩해야한다.

def combination(lst,n):
    for i in range(len(lst)):
        if n == 1:
            yield [lst[i]]
        for j in combination(lst[i+1:], n-1):
            yield [lst[i]] + j
            
for i in combination(a,2):
    print(i,end="")

내가 직접 작성한 코드를 보면 n == 1이라는 종료조건을 가진 재귀호출 알고리즘이다. 이렇게 조합 알고리즘을 직접 만들고나서 전체적인 코드를 작성하였다.

t = int(input())
a_i_com=[]
b_i_com=[]
t_max=[]
dp = [[0] for i in range(2**t)]
a_i = []
b_i = []
for i in range(t):
    a_i_, b_i_ = map(int, input().split())
    a_i.append(a_i_)
    b_i.append(b_i_)
 
def combination(lst,n):
    for i in range(len(lst)):
        if n == 1:
            yield [lst[i]]
        for j in combination(lst[i+1:], n-1):
            yield [lst[i]] + j
            
for j in range(1,t+1):
    for i in combination(a_i,j):
        a_i_com.append(sum(i))
    for i in combination(b_i,j):
        b_i_com.append(sum(i))
        
dp[0]=[a_i_com[-1],0]
dp[2**t-1]=[0,b_i_com[-1]]
for i in range(1,2**t-1):
    dp[i] = [a_i_com[i-1],b_i_com[(2**t-2)-i]]
    
for i in range(len(dp)):
    t_max.append(max(dp[i]))
    
min(t_max)

 위와 같은 코드로 jupyternote에서는 이상없이 잘 실행된다. 하지만 BOJ 홈페이지에서는 시간초과가 나왔다. 아무래도 재귀호출에는 호출한만큼의 for문이 쓰이기 때문에 시간초과가 발생한거 같다. 그래서 혼자 계속 고민하다가 C++을 사용하여 문제를 푼사람들의 아이디어를 찾아보았고 괜찮은 아이디어를 발견했다.

blog.naver.com/PostView.nhn?blogId=njw1204&logNo=221669613809

\(a_i\)를 무게로(Weight) \(b_i\)를 가치(Value)로 생각해서 냅색(Knapsack)문제로 해결했다는 아이디어다. 냅색으로 생각하고 풀면 확실히 Over time이 개선이 될것이다. 괜찮은 아이디어라고 생각하고 알고리즘을 짜봤는데 가방의무게한도 K 가 이 문제에서는 어떻게 적용해야할지 모르겠다... 따라서 다음 알고리즘 포스팅에서는 냅색알고리즘을 한번 정리해야겠다.