회의실 배정 2 - 19621

Seongjin Jo·2023년 5월 29일
0

Baekjoon

목록 보기
32/51

문제

풀이

package Baekjoon;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

// 회의실 배정 - S2

public class ex19621 {
    static int n;
    static int[] arr;
    static int[] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        arr = new int[Math.max(2,n)];
        dp = new int[Math.max(2,n)];

        for(int i=0; i<n; i++){
            int st = sc.nextInt();
            int et = sc.nextInt();
            int num = sc.nextInt();
            arr[i] = num;
        }

        // 테이블 정의
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0],arr[1]);
        for(int i=2; i<dp.length; i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+arr[i]);
        }
        System.out.println(dp[n-1]);

    }
}

처음에 정렬로 문제 풀이 시도.. 근데 답을 찾아가는 과정에서 비교가 필요한 거 같아서 풀이 방식에 의심을 가졌다.. 그래서 다시 생각해본 결과 이 문제는 DP로 해결해야하는 문제였다.

k강의가 있다고 치면 이 강의는 k+1,k-1 강의와 겹친다. 강의 시간이 겹치면 안되기 때문에 겹치지 않게 DP방식으로 문제를 해결하면 된다.

DP의 기본은 우선 테이블 정의다. dp[]는 인원수 값을 저장하는 배열이며, dp[1]에는 0번째 강의나 1번째 강의 둘중에 하나 큰 값을 넣어주면 된다. --> 점화식을 찾을수있다.

dp[2] 부터는 이제 비교를 해줘야한다. dp[i-1]을 고르거나 dp[i-2]에다가 arr[i]를 더해준 값의 최대값을 계속 해주어야 한다.

DPDPDPDPDPPDP,,;;

0개의 댓글