[백준 9375] 패션왕 신해빈 (JAVA)

백준 9375번 문제 - 패션왕 신해빈

9375번: 패션왕 신해빈

---

문제 분석

 

•  
• 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있는지 날짜를 출력해라.
• n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

---

해결 포인트

•  
• TreeMap으로 의상 종류에 따른 개수 구하기 
  • key가 의상 종류 | value가 해당 의상 종류 개수
• value만 가져오기
  • ArrayList<Integer> values = new ArrayList<>(clothes.values());
• 방법 1 : 재귀 함수 사용 (조합) → 실패 ! 시간초과 !
  • 조합 최대 개수(size)와 현재 조합에 사용된 개수(count), 현재 몇번째 의상 종류인지(n) 을 인자로 주는 조합을 구하는 재귀 함수 구현

public class Main {
    public static void main(String[] args) {

        long sum = 전체 의상 개수;

        ArrayList<Integer> values = new ArrayList<>(clothes.values());

        for (int i = 2; i <= values.size(); i++) {
            for (int j = 0; j < values.size(); j++) {
                sum += combination(values, i, 1, j);
            }
        }
	bw.write(sum + "\n");
    }

    public static int combination(ArrayList<Integer> values, int size, int count, int n) {
        if (count >= size) {
            return values.get(n);
        }

        int sum = 0;
        for (int i = n + 1; i < values.size(); i++) {
            sum += combination(values, size, count + 1, i) * values.get(n);
        }

        return sum;
    }
}

 

• 방법 2 : 해당 종류 옷을 벗는 경우까지 해서 모든 경우의 수 구하기 → 성공
  • 각 옷 종류 별 개수 + 1 해서 모든 종류를 곱한다.
  • 모두가 벗는 경우 1를 빼준다.

long sum = 1;

ArrayList<Integer> values = new ArrayList<>(clothes.values());

for (int i = 0; i < values.size(); i++) {
    sum *= values.get(i) + 1;
}
bw.write(sum-1 + "\n");

---

코드

 

import java.io.*;

public class Main {
    public static int N;
    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());

        int [] stairs = new int[N+1];
        for (int i = 1; i <= N; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }

        int [] dp = new int[N+1];
        dp[0] = 0;
        dp[1] = stairs[1];
        if(N >= 2) {
            dp[2] = stairs[1] + stairs[2];
        }
        for (int i = 3; i <= N; i++) {
            dp[i] = Math.max(dp[i-3] + stairs[i-1], dp[i-2]) + stairs[i];
        }

        bw.write(dp[N] + "\n");

        bw.flush();
        bw.close();
    }

}