[BOJ] 11052번: 카드 구매하기

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

2020.06.01 (월)

자체 테스트는 통과하나 채점 실패

 

/* import ... */
import java.io.IOException;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        while (true) {
            Scanner sc = new Scanner(System.in);

            int n = sc.nextInt();
            sc.nextLine();

            String input = sc.nextLine();

            String[] array = input.split(" ");
            HashMap<Integer, Float> map = new HashMap<>();

            for (int i = 0; i < n; i++) {
                map.put(i+1, Float.parseFloat(array[i]) / (i+1));
            }

            System.out.println(findMaxCost(map, n));
        }
    }

    public static float findMaxCost (HashMap<Integer, Float> map, int n) {
        int numberOfCard = 0;
        float expensiveValue = 0;
        Float max = 0.0f;

        if (n == 1) {
            max = map.get(1) * 1;
        } else if (n == 2) {
            if (map.get(1) > map.get(2)) {
                max = map.get(1) * 2;
            } else {
                max = map.get(2) * 1;
            }
        } else {

            for (int key : map.keySet()) {
                if (map.get(key) > expensiveValue) {
                    expensiveValue = map.get(key);
                    numberOfCard = key;
                }
            }

            if (numberOfCard == 1) {
                return max = expensiveValue * n;
            } else if(numberOfCard == n) {
                return max = expensiveValue * n;
            } else if (n % numberOfCard == 0) {
                return max = expensiveValue * n;
            } else {
                if (n <= 0) {
                    return 0;
                } else {
                    for (int i = 1; i <= n; i++) {
                        if (map.get(i) > expensiveValue) {
                            expensiveValue = map.get(i);
                            numberOfCard = i;
                        }
                    }
                    return (expensiveValue * numberOfCard + findMaxCost(map, n-numberOfCard));
                }
            }
        }
        return Math.round(max);
    }
}

 

테스트 코드는 동작하나, 백준 사이트에서 틀렸습니다로 결과 나옴... 띠로리

 

코드의 가독성도 좋지 않아 간결하게 짤 수 있도록 DP로 다시 풀어보았습니다.

 

/* import ... */
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        sc.nextLine();

        int[] input = new int[n+1];
        int[] d = new int[n+1];

        for (int i = 1; i <= n; i++) {
             input[i] = sc.nextInt();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                d[i] = Math.max(d[i], d[i - j] + input[j]);
            }
        }

        System.out.println(d[n]);

        sc.close();
    }
}

 백준 채점 성공!!