공부 123일차: 백준 11052번 카드 구매하기 자바 java

11052 카드 구매하기

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

11052번: 카드 구매하기

 

 

 

 

---

백준 11052번 문제 카드 구매하기

---

문제

---

 

 

 

 

---

오답

---

 

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{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        
        // 인덱스에 n이 들어가야 하므로 배열의 크기는 n+1
        int[] max = new int[n+1];    //최댓값 구할 배열
        int[] pack = new int[n+1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < n+1; i++) {
            pack[i] = Integer.parseInt(st.nextToken());
        }
        //System.out.println(Arrays.toString(pack));
        
        for(int i = 0; i < n+1; i++) {
            max[i] = pack[i] + pack[n-i];
        }
        Arrays.sort(max);
        System.out.println(max[n]);
    }
 
}
 

 

단순하게 생각했다가 틀렸다

 

 

---

정답 인정 코드

---

 

https://smartpro.tistory.com/53

이 블로그에 설명이 잘 되어 있었다

 

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{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int n = Integer.parseInt(br.readLine());
        
        // 인덱스에 n이 들어가야 하므로 배열의 크기는 n+1
        int[] dp = new int[n+1];    //최댓값 구할 배열
        int[] pack = new int[n+1];
        
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i < n+1; i++) {
            pack[i] = Integer.parseInt(st.nextToken());
        }
        // System.out.println(Arrays.toString(pack)); 디버깅
        
        for(int i = 1; i < n+1; i++) {
            for(int j = 1; j < i+1; j++) {
                dp[i] = Math.max(dp[i], pack[j]+dp[i-j]);
            }
        }
 
        System.out.println(dp[n]);
    }
 
}
 

 

지금껏 푼 동적계획법 문제들 규칙이 생각보다 덜 복잡해서 단순하게 생각하고 풀었더니, 배열 두 개 만들어지는 걸 생각도 못했다

 

 

 

---