BOJ 백준 5444 시리얼 넘버

문제 : https://www.acmicpc.net/problem/5444

 

[ 문제 요약 ]

- 기타 시리얼 넘버 값이 주어질 때, 시리얼 넘버의 합이 M의 배수가 되는 것들 중 기타 개수의 최대치를 출력하는 것

 

[ 테스트 케이스 설명 ]

2	// 테스트 케이스
3 5	// 기타개수(1<=500), 기준 값(1<=100,000)
1 8 6	// 시리얼 넘버(0<=100,000)
6 9	// 테케 반복
8 6 4 1 2 3

 

 

[ 문제 풀이 ]

 

시간 복잡도를 생각하지 않고 단순 dp를 선언한다면 아래와 같이 선언할 수 있습니다.

 

dp[기타 시리얼 넘버의 합] = 최대 기타 개수

 

하지만 위처럼 만들면 시간 초과입니다.

 

이유는 기타 시리얼 넘버의 합이 최대 5천만이고, 기타가 최대 500개 있을 수 있어서

 

2중 for 문으로 만들면 아래와 같은 코드가 되고 최악의 경우 250억 번 반복합니다.

 

 

[ 시간 초과 코드 ]

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());	// 테스트케이스
		while(T-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N	= Integer.parseInt(st.nextToken());	// 기타개수(1<=500)
			int M	= Integer.parseInt(st.nextToken());	// 기준 값(1<=100,000)
			int S[] = new int[N + 1];					// 기타의 시리얼 넘버(0<=100,000)
			int total = 0;
			
			st = new StringTokenizer(br.readLine());
			for(int i=1; i<=N; i++)
				total += S[i] = Integer.parseInt(st.nextToken());
			
			int dp[] = new int[total + 1];
			
			dp[0] = 1;
			// 최악의 경우 25,000,000,000
			for(int i=1; i<=N; i++)					// 최대 500
				for(int j=total; j>=S[i]; j--)		// 최대 50,000,000
					if(dp[j - S[i]] != 0)
						dp[j] = Math.max(dp[j - S[i]] + 1, dp[j]);
			
			int max = 0;
			for(int m=M; m<=total; m+= M)
				max = Math.max(max, dp[m]);
			
			sb.append(max - 1).append('\n');
		}
		System.out.print(sb);
	}
}

 

 

시간을 줄이기 위해서 시리얼 넘버의 합을 M 초과로 두지 말고, M으로 나눈 나머지로 하면 문제 해결이 가능합니다. 

 

dp[시리얼 넘버 합의 나머지] = 기타 최대 개수

 

그리고 이 문제에 대해서 알아둬야 할 것은 시간 복잡도뿐만 아니라 공간 복잡도도 생각해야 합니다. 

 

무작정 2차원 배열 선언 시 메모리 초과입니다.

 

아래 코드처럼 만들어야 합니다. 설명은 주석으로 대신합니다.

 

[ 정답 코드 ]

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());	// 테스트 케이스
		while(T-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N	= Integer.parseInt(st.nextToken());	// 기타 개수(1<=500)
			int M	= Integer.parseInt(st.nextToken());	// 기준 값(1<=100,000)
			int S[] = new int[N];						// 기타 시리얼 넘버(0<=100,000)
			
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<N; i++)
				S[i] = Integer.parseInt(st.nextToken());
			
			// 현재 연산 기준이 될 dp와, dp배열을 통해 만들어갈 nextDp선언
			int dp[]	= new int[M];
			int nextDp[]= new int[M];
			
			// 두 배열의 값을 처음에 모두 -1을 넣어 유효하지 않은 값으로 만들어 줍니다.
			for(int i=0; i<M; i++)
				dp[i] = nextDp[i] = -1;
			
			// dp[0] 을 0으로 초기화 하여 유효한 값으로 만들어줌
			dp[0] = 0;
			// 기타 반복
			for(int s : S)
			{
				// 시리얼 넘버의 합의 나머지 값을 반복
				for(int j=0; j<M; j++)
				{
					if(dp[j] < 0)	// 유효하지 않은 값이면 스킵
						continue;
					
					// 현재 나머지 값에서 s를 선택했을때 나머지 값
					int next = (j + s) % M;
					// 현재 dp를 통해 nextDp에 값을 갱신해나감 
					nextDp[next] = Math.max(nextDp[next], dp[j] + 1);
				}
				// 만들어진 nextDp를 dp값에 복사하여 연산반복
				for(int i=0; i<M; i++)
					dp[i] = nextDp[i];
			}
			// M의 배수이므로 dp[0] 값이 정답
			sb.append(dp[0])
				.append('\n');
		}
		System.out.print(sb);
	}
}