[백준] 11052번 : 카드 구매하기

문제

 

 

접근 방식

카드를 n개 살 때, 가장 돈을 많이 쓰는 경우를 구해야 한다.

 

i번째 카드팩에는 카드가 i개 들어있다 했으니

만약 카드를 4개 사야한다 가정하면

1번팩 + 1번팩 + 1번팩 + 1번팩
1번팩 + 1번팩 + 2번팩
1번팩 + 3번팩
2번팩 + 2번팩
4번팩

 

위와 같은 경우의 수가 만들어진다.

 

4개가 아닌 3개로 줄여보면 다음과 같을 것이고

1번팩 + 1번팩 + 1번팩
1번팩 + 2번팩
3번팩

 

2개로 줄이면 다음과 같다.

1번팩 + 1번팩
2번팩

 

1개면 당연히 1번팩 하나만 살 수 있다.

 

결국 n개를 고를 때 i번 팩을 골랐다면 n-i개를 고를 수 있고

(i번 팩값 + n-i개를 고를 수 있는 경우 가장 큰 값) 이 된다.

 

이를 dp[i]를 채울 때마다 1번 팩을 고른 경우부터 i번 팩을 고른 경우까지 비교하면서

가장 큰 값을 채워주면 되고 하나를 고르고 두 개를 고르나 두 개를 고르고 하나를 고르나 같기 때문에

i번까지 비교할 필요도 없이 i/2번까지만 비교해줘도 괜찮다.

 

이를 점화식으로 표현하면 다음과 같다.

j = 1; j  <= i/2; j++
dp[i] = (max(dp[i], dp[j] + dp[i-j]))

 

확실히 DP 문제를 많이 풀다 보니 경우의 수를 적다보면 규칙이 보이게 되는거 같다

PS는 그냥 많이 풀어보는게 답...

 

풀이

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());
        int[] dp = new int[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.parseInt(st.nextToken());
            for (int j = 1; j <= i; j++) {
            	dp[i] = Math.max(dp[i], dp[j] + dp[i - j]);
            }
        }

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