백준 2632 피자 판매 (Java)

1. 문제 링크

2632번: 피자판매

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. 피자 조각별 크기를 입력받고 저장하면서 총 크기를 저장한다.
2. 연속적으로 피자 조각을 더해야 하기 때문에 DP 느낌으로 생각했다.
3. 시작 숫자에 따라 연속적으로 이어질 때 항상 마지막 경우는 피자 전체를 의미하기 때문에 뺐다.
4. 피자 전체 조각에서 i+j를 나눠서 배열을 2배 길게 넣은 느낌으로 풀었다.
5. 그때 나온 값이 원하는 크기보다 작으면 해당 크기의 dp를 한다.
6. 두 피자로 각각 만들 수 있는 크기의 개수가 dp에 저장되어 있다.
7. 각 피자의 개수를 더했을 때 원하는 크기가 나오는 조합의 수를 더해서 출력했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int result = 0;
		int want = Integer.parseInt(br.readLine());
		String[] split = br.readLine().split(" ");
		int M = Integer.parseInt(split[0]);
		int N = Integer.parseInt(split[1]);
		int[] pizzaA = new int[M];
		int[] pizzaB = new int[N];
		int sumA = 0;
		for(int i=0;i<M;i++) {
			pizzaA[i] = Integer.parseInt(br.readLine());
			sumA += pizzaA[i];
		}
		int sumB = 0;
		for(int i=0;i<N;i++) {
			pizzaB[i] = Integer.parseInt(br.readLine());
			sumB += pizzaB[i];
		}
		int[] dpA = new int[want+1];
		int[] dpB = new int[want+1];
		dpA[0] = 1;
		dpB[0] = 1;
		int temp = 0;
		for(int i=0;i<M;i++) {
			temp = 0;
			for(int j=0;j<M-1;j++) {
				if(pizzaA[(i+j)%M]+temp > want) {
					break;
				}
				temp += pizzaA[(i+j)%M];
				dpA[temp]++;
			}
		}
		for(int i=0;i<N;i++) {
			temp = 0;
			for(int j=0;j<N-1;j++) {
				if(pizzaB[(i+j)%N]+temp > want) {
					break;
				}
				temp += pizzaB[(i+j)%N];
				dpB[temp]++;
			}
		}
		if(sumA>want) dpA[0] = 1; 
		else dpA[sumA] = 1;
		if(sumB>want) dpB[0] = 1; 
		else dpB[sumB] = 1;
		for(int i=0;i<=want;i++) {
			result+=dpA[i] *dpB[want-i];
		}
		System.out.println(result);
	}
}