[백준] 14606번 : 피자 (Small) – JAVA [자바]

https://www.acmicpc.net/problem/14606

14606번: 피자 (Small)

 

---

• 문제

 

 

---

• 문제 풀이

백준 14606번 피자 (Small)은 실버 4 난이도의 수학, 그리고 DP 문제이다. 이 문제는 그리고 2017 아주대학교 프로그래밍 경시대회 (APC) Division 2에 나온 B1번 문제였다. 이 문제는 간단한 점화식으로 푸는 게 가능하고 n의 범위가 워낙 작아서 꼭 DP를 이용해서 풀 필요도 없다. 

 

우선 문제에서 피자판의 개수 n이 주어진다. n의 범위는 1부터 10까지다. 피자판의 높이가 A라고 하면 이 피자판을 높이가 B와 C로 분리를 할 수 있다. 이런 행동을 하였을 때, B × C의 즐거움을 느낀다. 그리고 갑은 이 피자판을 모든 피자판들이 높이가 1이 될 때까지 분리를 한다.

 

계속해서 분리를 하니까 우선 재귀 함수가 떠오를 것이다. 하지만 이 문제를 재귀 함수로 풀면 너무 느리기 때문에 DP로 푼다. 높이 A의 피자판을 어떻게 나누는지는 중요하지 않다. 높이 1, A - 1로 나누든 높이 2, A - 2로 나누든 다 값은 같다. 

 

우선 int형 배열 dp를 만든다. dp [n]은 높이가 n일 때 n일 때 얻을 수 있는 최대의 즐거움이라고 정의하겠다. 그리고 피자판의 높이가 n일 때 항상 피자판을 높이 1, n - 1로 나눈다고 가정하겠다.

 

이제 다음과 같이 점화식을 쓸 수 있다. dp [n] = (n - 1) + dp [n-1]

 

이 점화식을 이용해서 예제들을 한 번 풀어보겠다.

 

EX 1) n = 1

높이가 1일 때 더 분리를 할 수 없으므로 값은 0이다.

 

EX 2) n = 3

dp [3] = 2 + dp [2] = 2 + (1 + dp [1]) = 2 + (1 + 0) = 3

따라서 값은 3이다.

 

EX 3) n = 5

dp [5] = 4 + dp [4] = 4 + (3 + dp [3]) = 4 + (3 + 3) = 10

따라서 값은 10이다.

 

EX 4) n = 8

dp [8] = 7 + dp [7] = 7 + (6 + dp [6]) = 7 + (6 + (5 + dp [5])) = 7 + 6 + (5 + 10) = 28

따라서 값은 28이다.

---

• 코드

 

import java.io.*;
import java.util.*;
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());
        int[] dp = new int[11];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = i-1 + dp[i-1];
        }
        System.out.print(dp[n]);
    }
}

 

---

• 문제

다른 DP 문제들을 이전에 풀어봤으면 쉽게 접근할 수 있는 실버 4 난이도의 DP 문제였다.