[자바] 백준 11052 카드 구매하기. 2021-07-22

 

 

 

 우선 DP 문제를 많이 연습해서 그런지, 처음보다는 문제 풀이 방법이 비교적 쉽게 떠올랐다.

우선 DP[i]=num 의 의미를 정의하고 시작하면 풀이법이 자연스럽게 떠오르기 마련인데, 난 i개를 뽑을때 최댓값 num이라고 정의했다. 그리고 DP[N]과 DP[N-1] 의 관계를 나타내면 끝인데, 내가 dp[1]부터 해본 결과 dp[n]= 두 수를 더해서 n을 만드는 수를 인덱스를 가지는 dp배열의 두 값의 합들중 가장 큰 값, 입력받은 arr[i]과 비교해서 큰 값이였다.

다시 쉽게 풀면 dp[5]를 구하려면, dp[1]+dp[4], dp[2]+dp[3]중 가장 큰 값과 숫자카드팩의 갯수를 한번에 맞출수 있는 arr[i] 의 값중 큰 것이다.

왜냐하면 내가 dp[i]는 i를 뽑을 때 가장 큰 값으로 정의했으니, 해당 숫자 N의 최댓값을 이루는 것을 단순 더해서 N을 만드는 두 수의 dp값의 덧셈으로도 최댓값을 만들수 있기 때문이다. 그래서 모든 경우의 수를 더한 후, 가장 큰 값을 뽑아주면 된다.

처음에는 dp[n]=dp[n-1]+dp[1] 이렇게 dp 식을 세웠는데, 이것은 더해서 n을 만드는 두수의 경우중 1개만 고른 경우라 틀렸음을 알게 되었다. 즉 dp[4]를 구한다 했을때 dp[3]+dp[1]보다 dp[2]+dp[2] 가 클수도 있다는 사실을 간과한 것이다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
       int N=s.nextInt();
        int[] arr = new int[N+1];
        int[]  dp=new int[N+1];
        for (int i = 1; i <= N; i++) {
            arr[i]=s.nextInt();
        }
        dp[1]=arr[1];
        for (int i = 2; i <= N; i++) {
            int cal=Calculator(i,dp);
            dp[i]=Math.max(cal,arr[i]);
        }
        System.out.println(dp[N]);
    }
    static int Calculator(int n,int[] dp){
        int max=Integer.MIN_VALUE;
        for (int i = 1; i <= n / 2; i++) {
            max=Math.max(dp[i]+dp[n-i],max);
        }
        return max;
    }

}

 

공부시간 1시간 20분.

순공시간 1시간.

 

오늘은 오전에 병원 외근 다녀온다고, 오전공부를 하나도 못했는데 오후에 밀도있는 공부를 해서 뿌듯하다. 또 내가 불과 몇개월 전까지만 해도 dp문제 어려워서 못풀었는데, 이렇게 다른 풀이 참고 안하고 내 스스로 처음부터 끝까지 문제를 완벽하게 해결해보니, 내가 성장하고 있음을 느꼈다. 자존감이 많이 올라간 느낌이다. 또 오늘 요양원에서 처음으로 요양보호사 선생님중 한분이 살쪘다는 말이 아닌 운동해서 어깨가 넓어졌다라는 말을 했다. 들으니 너무 좋았다ㅎㅎㅎ. 다들 살쪘다고만 해서 내가 헬스 하는걸 모르는줄 알았는데 그래도 몸 좋아진 거를 알아봐준 사람이 생겨서 기뻤다. 그리고 나보고 전에는 체형이 중고등학생같았는데, 이제는 많이 자랐다고 말해줘서 넘 좋았다.