[SW Expert Academy] 1486. 장훈이의 높은 선반

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV2b7Yf6ABcBBASw

java 풀이

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static int answer;
    public static void dfs(int total, int now, int[] arr, int b){
        if(total>=b){
            answer=Math.min(total-b,answer);
        }else{
            for(int i=now+1;i<arr.length;i++){
                dfs(total+arr[i],i,arr,b);
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int tc=sc.nextInt();
        for(int i=1;i<=tc;i++){
            answer=Integer.MAX_VALUE;
            int n=sc.nextInt();
            int b=sc.nextInt();
            int[] arr=new int[n];
            for(int j=0;j<n;j++){
                arr[j]=sc.nextInt();
            }
            Arrays.sort(arr);
            for(int j=0;j<n;j++){
                int total=arr[j];
                dfs(total,j,arr,b);
            }
            System.out.printf("#%d %d\n",i,answer);
        }
    }
}

내 생각

• 파이썬으로 구현해보고 했으나 상당히 오래걸렸다. 전역 변수 선언 부분 부터, 전역변수를 사용하기 위해 함수를 static으로 바꾸고 또 Math.min 같은 함수도 처음 사용해 보았다.
• 그리고 마지막으로는 출력하는 부분에서 '\n' 개행문자를 안넣어서 찾느라 한참 걸렸다...
• 풀이시간 : 40분

---

python 풀이

def dfs(total,now):
    global answer
    if total>=b:
        answer=min(answer,total-b)
    else:
        for i in range(now+1,n):
            dfs(total+arr[i],i)

for tc in range(int(input())):
    n,b=map(int,input().split())
    arr=list(map(int,input().split()))
    arr.sort()
    answer=sum(arr)
    for i in range(len(arr)):
        total=arr[i]
        dfs(total,i)
        
    print("#"+str(tc+1)+" "+str(answer))

내 생각

• 오랜만에 DFS로 백트래킹을 하니 한참 걸렸다.
• 모든 경우의 수를 구하면서 나아가기 위해 DFS를 사용하여 경우의 수를 찾기로 하였따. 순서에 따라서 후에 붙는 정수만 찾아주면 되기 때문에 가능했다.
• 각 더하는 경우가 숫자마다 시작하는 경우가 다르므로 for문으로 하나씩 시작하게 하였고 숫자의 누적합이 목표치인 b보다 같거나 크면 답을 갱신하였다. 나머지 경우는 시작 인덱스의 뒷부분의 수를 전부 고려해보면 되기 때문에 for문을 사용하여 재귀를 걸어주었다.
• 풀이시간 : 50분