[백준/Baekjoon]<2292번> 벌집 [C/C++/Python][Class 2]

백준 2292번 벌집

 

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

---

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

---

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

---

제한

 

예제 입력 1

13

예제 출력 1

3

---

#문제 풀이 방법

1. 숫자 N(1 ≤ N ≤ 1,000,000,000)이 입력되고, 위와 같이 벌집구조일 때 1에서 N까지 가는 최소 개수의 방을 출력한다.

2. 일단 제한시간은 2초이고 계산 횟수는 최대 2억 번 정도로 생각.

3. 벌집구조인 것을 생각해봐야 한다.

4. 일단 그림에서 보이는 70까지 한번 대충 답을 찾아보자.

5.

N=1(1개): 1

N=2~7(6개): 2

N=8~19(12개): 3

N=20~37(18개) : 4

N=38~61(24개) :5

        ●

        ●

        ●

(규칙이 보인다......!)

 

7. N>1일 때,

(∑ 6i {from i=0 to i=k}) +2 ≤ N ≤(∑ 6(i+1) {from i=0 to i=k})+1 (k는 0 이상의 정수) 이면

답은 k+2인 것을 알 수 있다. 

8.

∑ 6i {from i=0 to i=k}+2= 3k(k+1)+2

∑ 6(i+1) {from i=0 to i=k}+1=3(k+1)(k+2)+1

 

 

반응형

 

#C/C++

#include <iostream>
using namespace std;
int main()
{
    int N;
    cin>>N;
    if(N==1)
    {
        cout<<1;
        return 0;
    }
    for(int k=0;;k++)
    {
        if((N>=3*k*(k+1)+2)&&(3*(k+1)*(k+2)+1)>=N)
        {
            cout<<k+2;
            return 0;
        }
    }
}

#Python

N=int(input())
if N==1:
    print(1)
    quit()
k=0
while k>=0:
    if(N>=3*k*(k+1)+2)and(3*(k+1)*(k+2)+1)>=N:
        print(k+2)
        break
    k+=1

---

#연산 횟수를 추측해보자

N에 따른 k 값의 범위

위의 값이 입력된 N에 따른 k값의 범위이다.

근데 이걸 문제 풀면서 바로 파악하기는 어렵지 않나(머리가 좋으면 쉬울 수도 있지......?)

그래서 좀 더 실전적(?)으로 추측을 해보자.

처음에 3k(k+1)+2≤ N ≤3(k+1)(k+2)+1까지 만족해야 함을 알아낸 상태에서

3k^2≤3k(k+1)+2≤ N이므로 (k≥0, N≥1)

k ≤sqrt(N/3) 일 것이다.

따라서 N이 10억이면 k ≤sqrt(10억/3)<2만. ( 시간 복잡도로는 O(sqrt(N))라고 표현할 수 있겠지......?)

따라서 시간이 넉넉할 것으로 추정해볼 수 있을 것이다.