[SW Expert] 3752. 가능한 시험 점수

생각

Github - https://github.com/hellojdh/Code/blob/master/src/swexpert/d4/Q3752.java

시험 점수가 주어진다. 해당 점수들을 가지고 가능한 시험점수들의 개수를 출력하여라.
모든 점수를 선택하지 않은 0점도 시험점수이다.

처음 생각

SW Expert의 D3 몇 개 부터 최적화를 상관안하고 풀면 못푸는 문제들이 나오기 시작한다.

▶ 글쓴이는 그런걸 잘 못합니다!

▶ 최근 DP에 관한 기초적인 문제를 풀지 못해서 기초 DP 문제들을 풀어보면서 익혀보고 있었는데 마침 문제를 둘러보다가 DP로 풀면 될것 같아서 풀어보았다.

다음 생각

주어진 시험 점수를 가지고 가능한 시험점수들을 모두 만들어주어야한다. 일반적인 접근을 했다면 모든 조합을 만들어주어서 점수들을 더해 주었을 것이다.

▶ 그리고는 시간초과를 얻었을 것이다!

다다음 생각

다이나믹 적으로 접근을해보면 단순히 시험 점수들을 점점 누적시켜주면 된다. 그렇다면 어떻게 누적시켜 주어야 할 까?가 문제가 된다.

▶ 점수의 개수를 바탕으로 각 점수별로 만들 수 있는 점수를 누적해 나갔다.

▶ 우선, 만들 수 있는 점수의 개수를 카운트하면 되므로 boolean형 배열을 들어온 점수로 만들 수 있는 최대 값 + 여분 만큼 만들어 주었다.

다다다음 생각

0점도 점수이므로 dp[0] = true를 기본으로 해준 뒤, 모든 점수 값을 더한 sum부터 0점 까지 각 점수마다 돌면서 dp[점수] = true 일 경우 현 기준이 되는 점수를 더해주어 새로운 점수를 true로 만들어 주었다.

▶ dp[점수 + 현 기준 점수] = true

▶ 0~sum이 아닌 sum~0으로 반복문을 돌아야한다. 0 부터 반복문을 돌릴경우 true로 만들어준 점수가 계속해서 누적이 되기 때문이다. 예를들어 현 기준점수가 1점일 경우, 맨 처음의 0점일 때와 만나 

dp[0+현 기준 점수 1점] = dp[1] = true가 된다.

그리고 반복의 index가 올라가면서(2,3,4...sum) 모든 점수가 true가 될 것이다. 

dp[1+현 점수 1점] = dp[2] = true

dp[2+현 점수 1점] = dp[3] = true.. 가 끝까지 반복 될 것이다. 한개의 점수를 무제한으로 사용할 수 있다면 상관이 없지만 1번 씩 사용가능하니 이 경우는 틀린 경우가 된다.

▶ 반대로 sum~0으로 뒤에서부터 진행을 해주면 0점일 때, dp[0+현 점수 1점] = dp[1] = true가 진행되고 현 점수에 대한 반복문이 끝나게 된다.

다다다다음 생각

무작정 푸는 문제는 점점 사라지고 있는 현 시대에서 여러 최적화 방법들이 조금은 어렵더라도 부딪혀봐야겠다.

방안

1) Java 풀이

package swexpert.d4;
 
import java.io.*;
import java.util.StringTokenizer;
 
public class Q3752 {
    static int n;
    static int[] arr;
    static int sum,result;
    static boolean[] dp;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int tc = Integer.parseInt(br.readLine());
        for(int z=1;z<=tc;z++){
            n = Integer.parseInt(br.readLine());
            arr = new int[n];
            StringTokenizer st = new StringTokenizer(br.readLine());
 
            sum = 0;
            for(int i=0;i<n;i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                sum += arr[i];
            }
 
            dp = new boolean[sum+10];
            dp[0] = true;
            // 각 점수별로 만들 수 있는 점수를 만들어 주자.
            for(int i=0;i<n;i++){
                for(int j=sum;j>=0;j--){
                    // 가능한 점수를 만나면 현 점수 더해주기
                    if(dp[j])
                        dp[arr[i]+j] = true;
                }
            }
            result = 0;
            for(int i=0;i<=sum;i++)
                if(dp[i]) result++;
            System.out.println("#"+z+" "+result);
        }
    }
}