[BAEKJOON]14606 피자 (Small)

문제 요약

• 알고리즘 분류: dp
• 난이도: Silver5
• 문제내용:
  • 피자 높이가 A일 때 B, C로 분리하면 B*C 만큼 즐거움이 있다. B, C에서 분리해서 추가로 즐거움을 더 할 수 있다. 
  • 피자 높이 N으로 주어 질때 최대 총합 즐거움을 구하여라\
• 사이트: https://www.acmicpc.net/problem/14606

14606번: 피자 (Small)

문제풀이

 이번 문제에는 모든 경우의 수를 구해서 풀기가 힘들다. 모든 경우의 수를 구하 O(N^N)개 이상으로 나올수 있다. 그래서 이번 문제는 DP로 풀어야 통과가 되는 문제이다. DP에 대한 자세한 설명은 아래글로 확인해보면 된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

문제 접근방법

 dp는 구현보다 아이디어를 요구하는 문제로서 생각만 한다면 코드 구현은 간단한다. 데이터가 최대 1000개이고 초당 2천만번 연산이 가능하다고 가정할때 O(N )으로 풀어야 통과가 될것이다. 일단 아래의 그림으로 보면 N 이 8일 경우를 확인 해보자.

 두개로 분리 할고나서 곱했을때 가장 큰 값으로 나오는 것이 반짤라서 나오는 수이다. 그럼 8에서 반으로 나누면 4 * 4 = 16이다. 그리고 4 , 4 피자에서 분리 했을때 가장 큰 값이 반으로 나누면 된다. 그럼 2 * 2 = 4가 나온다. 거기에 2로 반 나눠서 곱하면 1이 나온다. 그럼 16 + 4 + 4 + 1 + 1 + 1 + 1 = 28 나온다. 여기서 확인 해보면 8에서 반으로 짤린 4일때 큰 값을 두번 더해 주면 끝이다. 그럼 dp[N] = (N / 2 * N / 2) + dp[N / 2] * 2가 나온다. 하지만 홀 수 일때도 봐야 한다. 홀 수에서는 반으로 나누면 정수로 안된다. 홀수에 관한 것은 아래 그림으로 확인 해보자.

 N이 7일 때 가정 해보자 7에서 나눌때는 4, 3으로 나누면 가장 큰 값이나온다. 거기에 4일때 큰 값과 3일때 큰 값을 더 하면 끝이다. 그럼 아래 같은 식으로 변경 할 수 있다.

dp[N] = ((N // 2 + N % 2) * N // 2) + dp[N // 2 + N % 2] + dp[N // 2]

N // 2 + N % 2이렇게 한 이유는 2로 나눠서 나머지 나올 경우 뒤에 +1을 해주면 반에 근사하게 나눠서 구할 수 있다.

Code

Python

N = int(input())
dp = [0] * 11
dp[2] = 1

for i in range(3, N + 1):
    B = i // 2 + (i % 2)
    C = i // 2
    dp[i] = B * C + dp[B] + dp[C]

print(dp[N])

Java

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

public class Main {
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		long[] dp = new long[91];
		dp[0] = 0;
		dp[1] = 0;
		dp[2] = 1;

		int B, C;
		
		for(int i = 3; i <= N; i++) {
			B = i / 2 + (i % 2);
			C = i / 2;
			dp[i] = B * C + dp[B] + dp[C];
		}
		
		System.out.println(dp[N]);
		
	}
	
}