문제
풀이
처음에는 모든 경우의 수를 탐색하면서 Set에 추가하여 풀었지만 시간초과.
- 문제는 최대 100가지 이므로, 경우의 수는 2^100 이고 당연히 시간 초과가 발생한다.
DP를 사용하여 문제 해결
- 각 배점을 탐색하면서 만들 수 있는 경우의 수를 DP에 기록
- 해당 배점을 선택하기 이전까지 DP배열에 기록된 모든 값들 + 현재 탐색중인 배점을 DP 배열에 기록
- 위의 방식대로 계속해서 배점 탐색
최종적으로 DP 배열에 기록된 갯수를 출력
코드
import java.util.*;
// dp로 탐색
// 최대 점수만큼의 크기를 가지는 dp 배열 생성
// 1. 한 문제씩 선택
// 2. 해당 문제를 dp배열에 기록
// 3. 지금 까지 기록된 dp배열에 선택된 문제를 더한 값도 dp에 기록
// 4. 계속 문제 선택하면서 진행
class Solution{
static public void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
int T;
T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++){
// Input
int n = sc.nextInt();
int maxVal = 0;
int[] arr = new int[n];
for(int i = 0; i < n; i++){
arr[i] = sc.nextInt();
maxVal += arr[i];
}
// 탐색
int[] dp = new int[maxVal+1];
dp[0] = 1;
for (int point : arr){
int[] temp = dp.clone(); // dp 탐색하면서 업데이트 한 값이 반영되지 않도록 임시 배열에서 업데이트
for (int i = 1; i <= maxVal; i++){
if (dp[i] == 1 && i+point <= maxVal){
temp[point + i] = 1;
}
}
dp = temp;
dp[point] = 1;
}
// 갯수 계산
int answer = 0;
for (int selected : dp){
if (selected == 1) answer+=1;
}
// 출력
System.out.printf("#%d %d\n", test_case, answer);
}
}
}
실행 결과
'Algorithm' 카테고리의 다른 글
[SWEA/Java] 1226. [S/W 문제해결 기본] 7일차 - 미로1 (0) | 2024.06.02 |
---|---|
[SWEA/Java] 1210. [S/W 문제해결 기본] 2일차 - Ladder1 (0) | 2024.06.02 |
[프로그래머스] 정수 삼각형(Java) (0) | 2024.06.02 |
[프로그래머스] 기능개발(Java) (0) | 2024.06.02 |
[프로그래머스] 가장 많이 받은 선물(Java) (0) | 2024.06.02 |