BOJ 백준 10023 Mooo Moo

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

 

[ 문제 요약 ]

• 들판마다 소의 음량을 측정하여 주어집니다. 들판마다의 음량을 구하는 식은 [ (이 전 들판에서의 음량 - 1) + 현재 들판에 있는 소들의 음량 ]입니다.
• 소들은 종류가 있고, 소들마다 고유의 음량이 다릅니다. 들판에 있는 소들의 예상 숫자 중 최소인 값을 출력합니다.

[ 테스트 케이스 설명 ]

5 2	// 들판 수(1<=100), 품종 수(1<=20)
5	// 품종에 따른 음량 수
7	// 품종에 따른 음량 수
0	// 이하 들판에서의 녹음된 소리 
17
16
20
19
답 : 4

 

[ 문제 해설 ]

• 들판 하나하나마다 예상되는 소들의 최소수를 구해서 결과를 출력해 주면 됩니다. 이때 소의 수를 알 수 없는 경우 -1을 출력하고 바로 종료합니다.
• 현재 들판에 소가 만약 한 마리도 없는 경우는 연산을 스킵 합니다. 소가 한 마리도 없는 것은, 들판의 측청 음량 값 자체가 0이거나, 이전들 판의 음량에서 1을 뺀 값과 현재 들판 값이 같을 때입니다.
• 그리고 현재 들판에 소가 있다면, [이전 들판의 음량 - 1] 값보다 음량이 추가되는데, 추가된 음량만큼 계산해서, 그 음량을 만들기 위한 소들의 최솟값을 구해주면 됩니다.
• 소를 여러 마리 고를 수 있기 때문에 무한 배낭 문제입니다.

dp[음량] = 해당 음량을 만들 때 필요한 최소 소의 숫자

• 최소수를 구해야 하기 때문에 dp를 처음에 큰 값으로 초기화하여 사용합니다.
• 각 소들의 음량을 모두 사용해도, 해당 음량을 정확히 만들 수 없다면 -1을 출력하고 조기종료합니다.

아래는 정답 코드와 속도를 개선한 코드 2개를 보여줍니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());// 들판 수(1<=100)
		int B = Integer.parseInt(st.nextToken());// 품종 수(1<=20)
		int sound[] = new int[B + 1];	// 품종에 따른 소의 음량
		int total[] = new int[N + 1];	// 각 들판마다 얻은 음량
		
		for(int i=1; i<=B; i++)
			sound[i] = Integer.parseInt(br.readLine());	// 1<=100
		
		for(int i=1; i<=N; i++)
			total[i] = Integer.parseInt(br.readLine());	// 0<=100,000
		
		int ans = 0;
		for(int i=1; i<=N; i++)
		{
			if(total[i] + 1 == total[i-1])	// 해당 들판에 소가 없을 경우
				continue;
			// 추가된 음량
			int nowValue = total[i];
			// 이전 들판 값이 0이 아닌 경우 해당 값의 -1 만큼 빼준다.
			if(total[i-1] != 0)
				 nowValue -= (total[i-1] - 1);
			
			// nowValue안에 소들이 최소로 들어가야 한다. 만약 불가한 경우 -1출력
			// dp[음량] = 해당 음량에 가능한 최소 소의 숫자
			int dp[] = new int[nowValue + 1];
			
			Arrays.fill(dp, 1<<30);
			
			dp[0] = 0;
			// 무한 배낭 문제
			for(int j=1; j<=B; j++)
				for(int z=sound[j]; z<=nowValue; z++)
					dp[z] = Math.min(dp[z], dp[z - sound[j]] + 1);
			
			if(dp[nowValue] == 1<<30)
			{
				System.out.print(-1);
				return;
			}
			
			ans += dp[nowValue];
		}
		System.out.print(ans);
	}
}

 

[ 속도 개선 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main{
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		final int INF = 1<<30;
		int N = Integer.parseInt(st.nextToken());// 들판 수(1<=100)
		int B = Integer.parseInt(st.nextToken());// 품종 수(1<=20)
		
		
		int sound[] = new int[B + 1];	// 품종에 따른 소의 음량
		for(int i=1; i<=B; i++)
			sound[i] = Integer.parseInt(br.readLine());	// 1<=100
		
		
		int total[] = new int[N + 1];	// 각 들판마다 얻은 음량
		for(int i=1; i<=N; i++)
			total[i] = Integer.parseInt(br.readLine());	// 0<=100,000
		
		
		int maxNeed = 0;
		int need[] = new int[N + 1];
		for(int i=1; i<=N; i++)
		{
			if(total[i] + 1 == total[i-1])	// 해당 들판에 소가 없을 경우
				continue;
			// 추가된 음량
			int nowValue = total[i];
			// 이전 들판 값이 0이 아닌 경우 해당 값의 -1 만큼 빼준다.
			if(total[i-1] != 0)
				 nowValue -= (total[i-1] - 1);

			need[i] = nowValue;	// 결과적으로 구해야 하는 값을 저장해 나감
			// 구해야하는 가장 큰 값 저장
			maxNeed = Math.max(maxNeed, nowValue);
		}
		
		int dp[] = new int[maxNeed + 1];
		
		Arrays.fill(dp, INF);
		
		dp[0] = 0;
		
		for(int s : sound)
			for(int i=s; i<=maxNeed; i++)
				dp[i] = Math.min(dp[i], dp[i - s] + 1);
		
		int ans = 0;
		
		for(int i=1; i<=N; i++)
		{
			if(dp[need[i]] == INF)
			{
				System.out.print(-1);
				return;
			}
			ans += dp[need[i]];
		}
		
		System.out.print(ans);
	}
}

[ 개선 코드 해설 ]

들판마다 dp를 실행하지 않고, 최종적으로 구해야하는 음량들을 모아놓고, 한번에 dp를 실행하는게 변화 포인트 입니다.

 

[ 속도 차이 ]

속도 차이가 2배 이상 나는 것을 볼 수 있습니다.