[DFS] 트럭에 태울 수 있는 가장 무거운 값

문제 유형

최대 용량 c 값이 주어지고, w의 몸무게를 가진 n마리의 강아지를 트럭에 태우고 이동해야할 때, 트럭에 태울 수 있는 가장 무거운 값을 구하시오.

필요자료구조

int c // (강아지 수),
int arr[] // (각 강아지 몸무게 초기화),
int L // (현재 레벨),
int sum // (현재 레벨의 sum 값),
int c // (최대 용량 무게),
String answer // 정답을 반환할 변수
DFS() 메서드 // 핵심 로직

핵심 문제 해석

1. 합이 같은 부분집합 문제와 유사하다. 포함되는 강아지와 포함되지 않는 강아지의 경우를 고려할 때 깊이 탐색 정렬이 적합하다.
2. o, x로 생각하자면 현재 sum 값에 arr 배열 다음 레벨 값(다음 인덱스 값)을 저장 o, x

핵심 코드

public void DFS(int L, int sum){
	if(L == n) answer = Math.max(answer, sum);
    else{
    	DFS(L+1, sum+arr[L]);
        DFS(L+1, sum);
    }
}

알고리즘을 스택프레임으로 설명

개선된점

1) 문제 이해 능력 향상
2) 디버깅 적극 활용
3) 문제를 풀 때 어떤 자료구조가 필요한지 생각해보기 & 코드 리팩토링(필요 없는 코드, 변수 삭제)

1. 문제 이해 능력 향상
어제 불었던 부분 집합이 서로 합이 같은 경우 문제와 비슷한 양상의 문제로 해석되었음.

문제에서 주어지는 최대 용량 = c 값은 합이 같은 부분집합 문제의 total과 유사한 조건이라고 판단하에 문제를 풀었음.

DFS 깊이 탐색 정렬의 핵심은 모든 인자가 뻗어나갈 수 있는 방향을 체크해보고 내가 원하는 조건의 값을 뽑아내는 것에 있음.

이 문제도 그와 유사한 형태라고 파악

2. 디버깅 적극 활용
이 문제를 풀 때 answer = sum; 해놨지만 answer가 0이 출력되는 문제 발생.

answer 값에 브레이크 포인트를 걸어놓고, sum 값이 왜 0이 들어가는지 과정 확인

알고보니 모든 DFS를 다 돌고 그때마다 answer = sum 해줬기 때문이었음. 그러니 스택프레임이 모두 빠져나갈 땐 0이 담길 수 밖에 없는 상황이었음.

코드를 보면 바로 이해가 됨.

 public void DFS(int L, int sum){
        if(sum > c) return;
        if(L == n){
            answer = sum; // 문제가 되는 부분
        }else{
            DFS(L+1, sum+arr[L]);
            DFS(L+1, sum);
        }

    }

문제가 되는 answer 코드를 아래와 같이 수정

 answer = Math.max(answer, sum); // 수정

3. 문제를 풀 때 어떤 자료구조가 필요한지 생각해보기 & 코드 리팩토링(필요 없는 코드, 변수 삭제)

문제를 풀면서 어떤 자료구조가 필요할지 코드로 짜보고 필요 없다 싶은건 과감하게 제거

마지막으로 정수형 c, n, answer, arr 배열이 필요하다는걸 깨닫고 코드 리팩토링 진행.

느낀점, 피드백, 개선할 점

1. 알고리즘은 계속해서 공부해야 한다. 너무 급급한 마음으로 많이 풀려고하지 말고 문제를 하나하나 이해하고 내것으로 만들면서 풀어나가자.