[백준 / 실버1] 11052 카드 구매하기 (Java)

Ilhwanee·2022년 10월 21일
0

코딩테스트

목록 보기
117/155

문제 보기



사용한 것

  • 점화식을 세워 문제를 풀이하기 위한 bottom-up


풀이 방법

  • dp[i]의 최대 값은 다음 중 최대 값과 같다.
    • arr[i] + dp[0]
    • arr[i - 1] + dp[1]
    • arr[i - 2] + dp[2]
    • 반복....
  • 따라서 이중 for문을 사용하여 점화식을 세워 dp[]n까지 점진적으로 계산하면 된다.


코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(line[i - 1]);
        }

        int[] dp = new int[n + 1];
        dp[1] = arr[1];
        for (int i = 2; i <= n; i++) {
            for (int j = i; j > 0; j--) {
                dp[i] = Math.max(arr[j] + dp[i - j], dp[i]);
            }
        }

        System.out.println(dp[n]);
    }
}


profile
블로그 이전 -> https://pppp0722.github.io

0개의 댓글