[DFS] 최대점수 구하기

문제 유형

n개의 문제와 제한 시간 m이 주어진다. 각 문제는 점수와 풀이 시간이 주어진다. 제한 시간 m안에 n개의 문제중 최대 점수를 얻을 수 있도록 해야 한다.

필요자료구조

int n // (문제 갯수),
int arr[][] // (n개의 문제),
int L // (현재 레벨),
int rowsum // (문제 점수의 합),
int colsum // (문제 풀이 시간의 합),
int m // (제한 시간 m),
DFS() 메서드 // 핵심 로직,
answer // 출력,

핵심 문제 해석

1. 다음 레벨로 이동했을 때 해당하는 레벨에 인덱스를 포함하느냐(o), 포함하지 않느냐(x)를 구하는 문제이다.
   이러한 유형의 문제는 DFS를 사용해서 풀 수 있다.

핵심 코드

public void DFS(int L, int rowSum, int colSum){
        if(colSum > m) return;
        if(L == n){
            answer = Math.max(answer, rowSum);
        }
        else{
            DFS(L+1, rowSum+arr[L][0], colSum+arr[L][1]);
            DFS(L+1, rowSum, colSum);
        }
    }

개선된 점

• 문제에서 요구하는 자료구조와 알고리즘을 파악했고 손이나, 메모장으로 자료구조를 그려보면서 문제를 풀이했다.
  그러다보니 어렵게 느껴졌던 문제도 자료구조가 그려지면서 감이 오기 시작했고,
  이차원 배열 자료구조를 선택하고,
  DFS 알고리즘을 그려보면서 어떤 매개변수가 들어갈지 선택할 수 있었다.

• DFS에서 o,x 방식을 사용한 문제를 풀이하는게 한결 쉬워졌다.

피드백, 개선할 점

1. 이차원 배열 자료구조 이해 및 응용능력 부족
   이차원 배열의 자료구조를 명확하게 응용할 수 있는 단계가 아니었다.
   그래서 10분 정도 고민하고 나서야 이차원 배열을 사용할 수 있었다.
   초기화하는 과정도 그리 쉽지 않았다.
   처음에는 열을 하나만 생성하도록 설정해줬는데 원하는 출력이 나오지 않아서 고민하다가 열을 두개로 선언했다.

느낀점

• 핵심 관건은 자료구조 설정과, 어떤 알고리즘을 선택하느냐인 것 같다.
  알고리즘 문제만 많이 풀게 아니라,
  자료구조 지식도 함께 공부해야할 것 같다.