[Java] SW Expert Academy 3752번 문제: 가능한 시험 점수 (Dynamic Programming, 동적 계획법)

--- 문제 ---

• 3752. 가능한 시험 점수
  • 제한 시간이 짧은 문제 (시간 최적화 필요)

--- 코드 ---

역시나, 처음에 DFS 방식으로 하나하나 맞았다,안맞았다로 풀어봤더니

시간 초과가 나왔습니다.

그래서 이 문제는 더 쉽게 동적 계획법으로 푸는 것이 맞다는 것을 알았습니다.

문제가 추가 되면서 생겨나는 숫자를 하나씩 Set 구조에 추가하는 방식입니다.

 

이는 다음과 같은 규칙 때문에 가능합니다.

예로 A = {a,b,c,} 라는 배점 배열이 있을 때를 보겠습니다.

 

문제 갯수 (n)	0	a	b	c	a+b	a+c	b+c	a+b+c
a 한 개 일때	0	a
a,b 두 개 일때	0	a	b		a+b
a,b,c 세 개 일때	0	a	b	c	a+b	a+c	b+c	a+b+c

위 표를 보시면 a가 한개일 때에서 a,b 두개로 바뀌면서

a가 한개 일때의 원소들에 +b를 한 값이 추가 되었습니다.

그리고 a,b 두개에서 a,b,c로 바뀌면서

a,b 두개 일때의 값들에서 +c를 한 값이 추가 되었습니다.

이렇게 하나 하나 배점을 추가해서 그 때마다 기본 요소에 배점을 더한 값을 Set에 추가하는 것 입니다.

 

이때, Set을 사용하는 이유는 중복되는 점수를 자동으로 제거해주기 때문 입니다.

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;

public class Sw3752 {
	public static HashSet<Integer> result;
	public static int[] scores;
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("./src/3752.txt"));

		Scanner sc = new Scanner(System.in);
		
		int T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++) {
			
			// 1. initialize
			int size = sc.nextInt();
			result = new HashSet<>();
			result.add(0);
			
			// 2. DP
			for(int i=0; i<size; ++i){
				int tmp = sc.nextInt();
				HashSet<Integer> copy = (HashSet<Integer>) result.clone();
				Iterator<Integer> pre = copy.iterator();
				while(pre.hasNext()) {
					result.add(pre.next()+tmp);
				}
			}
			
			// 3.Print result
			System.out.printf("#%d %d%n",test_case,result.size());
			
		}
	}
	
}

 

--- 출처 ---

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn&categoryId=AWHPkqBqAEsDFAUn&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy