<Algorithm> 176. 가능한시험점수(SWExpert)

1. 가능한시험점수(SWExpert)

   사용 알고리즘 :  DP

• 이 문제는 완전탐색을 생각하다가 계산해보니 연산이 너무 많아서 고민하다 힌트를 보고 풀었다.

• DP의 가장 큰 특징이 누적이니만큼 이러한 문제를 접근할때 어떻게 누적을 해야될지로 접근해보면 좋을것 같다. 

문제에 대한 접근&생각

1. 모든 점수가 나오는 경우의 수 -> 완전탐색? -> 점수가 100가지 총 2^100 연산 -> 불가능
2. 경우의 수를 최소화 -> 점수들은 이전 점수들과 관계가 있음 -> 누적!(DP)

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.util.Scanner;   public class Solution {       public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int test = sc.nextInt();         /****************************          * 이전 점수를 누적하여 현재 점수에 대해          * 더해서 누적하는 방법으로 점수의          * 경우의 수를 구한다.          ****************************/         for(int t = 1; t<=test;t++) {             int n = sc.nextInt();             int[] nums = new int[n];             int total = 0;             for(int i = 0; i < n; i++) {                 nums[i] = sc.nextInt();                 total+=nums[i];             }             boolean[] check = new boolean[total+1];             check[0] = true;             int cnt = 0;                      for(int i = 0; i < n; i++) {                 for(int j = total; j >=0; j--) {                     if(check[j]) {                         check[j+nums[i]] = true;                     }                 }             }             for(int i = 0; i <= total; i++) cnt = check[i]?cnt+1:cnt;             System.out.println("#"+t+" "+cnt);         }              } }   Colored by Color Scripter

cs

 

얻은 것

• String[] str = br.readLine().split(" ") 으로 token 대체 가능