Baekjoon (백준) 14501 번

📝 Beakjoon 문제

Baekjoon BruteForce 14501번 (퇴사)

• 처음 접근 DFS
• 정답을 비교 후 DP(다이나믹 프로그래밍) 도 있다는 것을 확인
• 두가지 방법의 풀이

<DFS>
public class Beak_j_14501 {

    public static int input[][]; // [0]시간과 [1]비용을 담을 2차원 배열
    public static int N; // 퇴사일
    public static int max; // return 값

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        input = new int[N][2];


        for(int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            input[i][0] = Integer.parseInt(st.nextToken());
            input[i][1] = Integer.parseInt(st.nextToken());
        }
        br.close();
        
		dfs(0,0)

        bw.write(max+"");
        bw.flush();
        bw.close();


    }

    public static void dfs(int T,int sum){

		// T의 길이가 N이상 일 경우
        if(T  >= N){ 
        	// 더한 값 가장 큰 값으 비교해서 함수 종료
            max = Math.max(sum,max); 
            return;
        }
        // T의 길이가 이하 일 경우
        if( T + input[T][0] <= N){ 
        
        	// 현재 위치에서 필요 시간 만큼 위치 이동
            dfs(T+input[T][0],sum+input[T][1]); 
        }
        else {
        	// T의 길이가 N보다 클경우 비용을 더하지 않음.
            dfs(T + input[T][0], sum);             
        }
        // 모든 경우의 수를 구하기 위해 T의 길이만 저장해서 다시 호출
        dfs(T+1, sum); 
    }

<DP>
int dp[] = new int[N+1];
        
        for(int i = 0; i < N; i++){
        	// 현재 위치 + 시간이 퇴사일 이하 일때
            if(i + input[i][0] <= N){ 
            
            // 이동한 한 값과 현재위치 값을 더한 값 중 큰 값 
            // : 현재값을 선택 여부를 판단하기 위함
                dp[i+input[i][0]] = Math.max(dp[i + input[i][0]], dp[i] + input[i][1]); 
                
            }
            
            // 현재 위치+시간이 퇴사일 보다 클 경우 이동할수 없음으로 
            // 현재 위치와 다음 위치중 큰 값을 다음 위치에 할당
            dp[i+1] = Math.max(dp[i],dp[i+1]); 
            
        }


        bw.write(dp[N]+"");
        bw.flush();
        bw.close();

💡 문제를 풀면서 느꼈던 점

• 본 문제는 Brute Force 문제이다. 당연히 DFS로 접근해야 할 것으로 예상

• 처음 알고리즘을 작성할 때 해당 위치를 선택 여부에 대해 고려하지 못함.

• 특히 Brute Force 문제 같은 경우에는 나올수 있는 상황이 더 있는지 없는지 확인해 볼 것.

• 문제를 풀기전 하나의 방법만 얽매이지 말고 다른 여러가지 알고리즘 고려해 볼 것.