[JAVA | 백준] #2292 벌집 🐝🏠

📍 벌집

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

 

 

 

✨ 방법1 ✨

 

문제의 그림을 방별로 표시해보았더니 규칙이 보였다.

 

 

i >= 2 일 경우, 이러한 점화식이 나온다. 근데 dp 아니고 그리디였다.
아무튼 dp의 크기를 N의 최대 크기인 10억으로 할 경우 메모리 초과가 난다.
따라서 N이 10억일 때 결과값인 18258에 1을 더해 18259로 초기화했다.

 

 

 

✨ 전체코드 ✨

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(sc.readLine());

        int answer = 0;
        int[] dp = new int[18259];

        dp[0] = 1;
        dp[1] = dp[0] + 6;

        if(N > 7) {
            for(int i=2; N > dp[i-1]; i++) {
                dp[i] = dp[i-1] + 6*i;
                answer = i;
            } answer += 1;
        } else answer = (N==1 ? 1 : 2);

        System.out.println(answer);
    }
}

 

 

 

🌀 성능

• 메모리 : 14,328 KB
• 시간 : 100 ms

 

 

 

🌟 방법2 🌟

 

N의 최대 크기는 10억이기 때문에 반복문은 비효율적이라고 생각했다.
시간 제한이 2초이기 때문에 첫 번째 코드는 시간초과가 나지 않았지만
메모리와 시간측면에서 반복문보다 식이 효율적이라고 생각해 식으로도 풀어봤다.

 

 

🌟 전체코드 🌟

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        int answer = (N==1 ? 1 : (int) Math.ceil((double)(3 + Math.sqrt(9 + 12.0 * (N - 1))) / 6.0));
        System.out.println(answer);
    }
    
}

 

 

 

🌀 성능

• 메모리 : 14,184 KB
• 시간 : 128 ms

 

 

 

⚡️ 방법3 ⚡️

 

 

 

⚡️ 전체코드 (gun0680님 코드) ⚡️

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        // 1 6 12 18 24 30 36 42 48 54 60...
        // 1 7 19 37 61
        int sum = 1;
        for (int i = 0; ; i++) {
            sum += i * 6;
            if (sum >= N) {
                System.out.println(i + 1);
                break;
            }
        }
    }
}

 

 

 

🌀 성능 🌀

• 메모리 : 11,488 KB
• 시간 : 64 ms

 

 

 

---

수학식으로 구현한 방법2보다 반복문으로 푼 방법1이 더 빨랐다.

Math.sqrt가 부동소수점 연산을 수반하기 때문에 계산이 비교적 느리다고 한다.

그리고 동일한 로직이지만 방법1보단 방법3의 코드가 훨씬 깔끔하다.