백준 피자판매(2632)

피자판매

1. 힌트

1) 피자에서 연속적인 조각들을 골라야하는데, 피자는 원형이기 때문에 한 바퀴에 걸쳐서 고르는 경우도 있음에 유의해야 합니다.

2) 연속적인 구간의 합은 누적 합을 이용하면 $O(1)$에 구할 수 있고, 연속적인 구간의 수는 $O(N^2)$개입니다.

3) 연속적인 구간의 합은 최대 $1000 \times 1000$이므로 $R[x] =$길이가 $x$인 구간을 고르는 경우의 수라는 배열을 정의할 수 있습니다.

2. 접근

1) $A$피자 $B$피자 경우의 수 구하기

$A$피자와 $B$피자 각각에 대해서 피자를 고를 수 있는 경우의 수를 미리 구해놓으면 전체 경우의 수를 쉽게 구할 수 있습니다.
$R1[x] =$$A$피자에서 길이가 $x$인 연속한 구간을 고르는 경우의 수
$R2[x] =$$B$피자에서 길이가 $x$인 연속한 구간을 고르는 경우의 수로 정의하면
$x$는 최대 $1000 \times 1000$이므로 배열을 선언할 수 있습니다.

손님이 구매하고자 하는 피자크기 $K$에 대해 $R1[x] \times R2[K - x]$를 구해서 모두 더해주면 됩니다. 이 때, $A$혹은 $B$피자에서 아예 고르지 않는 경우의 수도 있음에 유의합니다.

2) 원형에서 연속한 구간 고르기

임의의 $N$길이의 구간에서 모든 연속한 구간을 고르는 경우의 수는 $O(N^2)$입니다. 원형이 아니였다면 $i \le j$인 $R[i, j]$를 모두 구하면 되겠지만 원형이라서 시작점에 걸치는 경우도 있다는 것을 고려해야합니다. 경우의 수가 중복되지 않도록 여기서는 길이 $k$를 정하고 길이별로 구분해서 모든 경우의 수를 구합니다. 단 $k=0$인 경우와 $k=N$인 경우는 예외처리 해줍시다.

이렇게 구하다 보면 길이 $k$가 길어서 배열의 바깥을 나가는 경우가 있습니다. 이럴 때는 배열 바깥에서 튀어나온 만큼 처음에서 다시 시작하게 하면 됩니다.

3. 구현

public class Main {

	// 피자판의 모든 원소를 연속적으로 선택해서 만들수 있는
    	// 경우의 수를 나타내는 배열 반환
	static int[] f(int N, int[] S) {
		int[] ret = new int[1000001];
        	// 하나도 안 선택하는 것도 경우의 수 중 하나
		ret[0]++;
		for (int i = 1; i <= N; i++)
        		// 길이가 k인 구간을 선택
                	// 단 전체 구간은 중복 될 수 있으므로 예외
			for (int k = 1; k <= N - 1; k++)
            			// 한 바퀴 도는 경우
				if (i + k - 1 > N) {
					ret[S[N] - S[i - 1] + S[i + k - 1 - N]]++;
				} else {
					ret[S[i + k - 1] - S[i - 1]]++;
				}
		ret[S[N]]++;
		return ret;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int K = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] S1 = new int[N + 1]; int[] S2 = new int[M + 1];
		for (int i = 1; i <= N; i++) S1[i] = Integer.parseInt(br.readLine()) + S1[i - 1];
		for (int i = 1; i <= M; i++) S2[i] = Integer.parseInt(br.readLine()) + S2[i - 1];
		int[] R1 = f(N, S1); int[] R2 = f(M, S2);
		long ret = 0;
		for (int i = 0; i <= K; i++)
			ret += (long)R1[i] * R2[K - i];
		System.out.println(ret);
	}

}

1) 시간 복잡도

피자 $A, B$의 전처리에 $O(N^2)$
길이가 $K$인 피자를 만드는 경우를 모두 시도하는데 $O(K)$
$O(N^2 + K)$입니다.