코드트리 [자바 java] 적절한 옷 고르기

https://www.codetree.ai/missions/2/problems/select-proper-clothes?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 다소 복잡해보이는 문제이지만, 막상 풀이를 생각해보면 크게 어렵지는 않다.

 

문제에서 입력으로 옷 수, 해당 옷들의 화려함, 시작일, 종료일이 주어진다. 이 옷들을 입는 경우들을 적절하게 조합해서 만족도의 최댓값을 구하는 문제이다 .

 

나는 dp를 이차원배열로 만들고, 해당 일에 해당 옷을 입는 경우 중 가능한 가장 큰 값을 dp에 저장하도록 하였다. 위의 경우를 dp에 넣는다고 가정해보자.

옷/일수	1	2	3	4	5
1	0   A	D
2	0   B
3	0   C

1일차는 전날이 없으므로 dp값이 전부 0이다. 

D의 값을 구해보고자 하면, A,B,C중에서 1번 옷과 해당 번호의 차이  + 해당 DP값 중 가장 큰 값을 넣으면 된다.

이 때 주의할 점은 1일차에 1,2,3,번 옷을 사용 가능한지 여부와 2일차에 1번 옷을 사용할 수 있는지 여부이다. 만약 사용이 불가하다면 -1을 넣고 다음 배열을 탐색하도록 하였다.

이를 끝까지 하면 5일차에 123번 옷 dp값이 모두 찬다. 여기서 답은 123번 옷의 dp값 중 최댓값을 구하면 된다. 

 

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); //옷 개수
        int m = Integer.parseInt(st.nextToken()); //일수

       // st = new StringTokenizer(br.readLine());
        
        int[] start = new int[n]; //옷 별 시작일
        int[] fin = new int[n];//옷 별 끝일
        int[] w = new int[n];//옷 별 화려함

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            start[i] = Integer.parseInt(st.nextToken());
            fin[i] = Integer.parseInt(st.nextToken());
            w[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[n][m+1];
        

        for(int i = 2;i<=m;i++){
           
            for(int j = 0;j<n;j++){
                if(i < start[j] || i > fin[j]) {
                    dp[j][i] = -1;
                } //i일에 사용 x인 경우
                else{
                    int d = 0;

                    for(int k = 0;k<n;k++){
                        if(i-1 < start[k] || i-1 > fin[k]) continue; // 전날 해당 옷이 사용 불가인 경우
                        d = Math.max(d,Math.abs(w[k] - w[j]) + dp[k][i-1]);
                    }
                    dp[j][i] = d;
                }


            }
        }

        int ans = 0;
       
        
        for(int i = 0;i<n;i++){
            ans = Math.max(ans,dp[i][m]);
        }

        System.out.println(ans);


    }
}