BOJ) 카드 구매하기

카드 구매하기

11052번: 카드 구매하기

풀이

 

갑자기 dp문제를 풀고싶어서 이 문제를 풀었다.

이 문제는 한번에 정답을 맞추지 못했다.

총 세번을 제출했는데, 

첫번째는, 에라토스테네스의 체를 이용해서 소수를 판별하는 것처럼, 특정 인덱스 i 에서 n까지 i 씩 증가하면서 초기에 저장된 가격과 i를 여러번 곱한 값 중 더 큰 값을 저장해주었다.

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

한 6%? 정도에서 틀린 것 같다.

 

두번째는, 1부터 인덱스를 돌면서 특정 인덱스 n이 있다면, n-1까지 조합 중 가장 큰 수를 저장해줬다.

이 때, 홀수번 index와 짝수번 idx을 구분해서 코드를 짰다.

 

카드가 7인 경우와 6인 경우를 살펴보면,

1 2 3 4 5 6 7 <  - 7 장의 최대 값을 찾아보려면,  1+6, 2+5, 3+4 을 검증해야한다.

1 2 3 4 5 6   < -  6 장의 최대 값을 찾아보려면, 1+5, 2+4, 3+3 을 검증해야한다.

 

 

7/2 = 3,    6/2 = 3  으로 두 중간 값이 같게 나온다.

거기에 7인 경우는 두 장씩 합이 딱 맞는데, 6인 경우에는 중간 값인 3 카드를 두 번 더해줘야한다.

 

그래서 짝수인 경우에는 먼저 중간 값에 2를 곱한 값과 최대값을 비교해줬다.

그 다음 중간값에 +1을 해주면서 짝에 맞게 검사할 수 있도록 설정했다.

 

for(int i=1; i<=n; i++) {
	int mid = i/2;
	if(i%2 ==0) {
		cards[i] = Math.max(cards[i], cards[mid]*2);
		mid++;
	}
	for(int j=mid; j<i; j++) {
		cards[i] = Math.max(cards[j]+cards[i-j], cards[i]);
	}
}

 

 

세번째는 위의 조합과정을 그냥 쌩 for문으로 돌렸다.

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

 

효율 측면에서는 2번과 3번이 크게 차이가 나지는 않는다.

더 편한 방식으로 풀면 되는데, 2번이 생각하기 더 편한 것 같다.

 

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        solution(new BufferedReader(new InputStreamReader(System.in)));
    }

    private static void solution(BufferedReader br) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=1; i<=n; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<=n; i++) {
            int mid = i/2;
            if(i%2 ==0) {
                cards[i] = Math.max(cards[i], cards[mid]*2);
                mid++;
            }
            for(int j=mid; j<i; j++) {
                cards[i] = Math.max(cards[j]+cards[i-j], cards[i]);
            }
        }

        System.out.println(cards[n]);
        br.close();
    }
}