[백준] 14607번 : 피자 (Large) – JAVA [자바]

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

14607번: 피자 (Large)

 

---

• 문제

 

 

---

• 문제 풀이

백준 14607번 피자 (Large)는 실버 3 난이도의 수학 문제이다. 이 문제의 알고리즘 분류에서는 DP도 같이 있지만 DP로는 못 푸는(?) 문제이다. 이 문제는 그리고 2017 아주대학교 프로그래밍 경시대회 (APC) Division 2에 나온 B2번 문제였다.

 

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

 

이전 문제인 피자 (Small)에서는 다음과 같은 점화식을 써서 풀었었다.

dp [n] = (n - 1) + dp [n-1]

 

하지만, 이 문제의 n의 범위는 1 ≤ n ≤ 10^9이다. 보통 시간 복잡도가 O(n) 일 때 10^7이나 10^8의 계산을 하면 1초가 소요되기 때문에 O(n)의 시간 복잡도를 가지고 있는 DP를 쓰면 시간 초과가 뜬다.

 

그래서 이 문제는 다른 수학 공식을 이용해서 풀 것이다.

바로 즐거움 = n(n-1) / 2이다.

 

EX 1) n = 1

즐거움 = 1(1-1) / 2 = 0

 

EX 2) n = 3

즐거움 = 3 (3 - 1) / 2 = 3 × 2 / 2 = 3

 

EX 3) n = 5

즐거움 = 5 (5 - 1) / 2 = 5 × 4 / 2 = 10

 

EX 4) n = 8

즐거움 = 8 (8 - 1) / 2 = 8 × 7 / 2 = 28

---

• 코드

 

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Integer.parseInt(br.readLine());
        System.out.print((n*n-n)/2);
    }
}

 

---

• 후기

이 문제는 도저히 안 풀려서 질문을 봤는데 이 공식이 있었다.