<알고리즘 문제풀이&연습>/[C++] 백준, 프로그래머스 등등

[백준 2292] 벌집

BlockDMask 2017. 9. 26. 16:36
반응형
  • 안녕하세요. BlockDMask 입니다.

  • 9월 25일자 문제 입니다.

0.제목

  • 백준 2292 벌집

  • BOJ 2292 벌집

1. 문제 설명


[사진 출처]

https://www.acmicpc.net/problem/2292
ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2004 B번


위 그림과 같이 육각형으로 벌집이 이루어져 있습니다.


중앙 1번 방에서 부터 옆방 옆방으로 1씩 증가하면서 번호로 주소가 써져있습니다. 


(1<= N <= 1,000,000,000)

범위의 숫자 N이 주어졌을때, 벌집의 중앙인 1번 방에서 N번 방까지 최소 몇개의 방을 지나가는지 계산하여 출력하면됩니다.


방의 개수는 시작방과 끝방도 포함입니다.


예를 들어

> 19번방이 N으로 들어오면 출력은 3 입니다.

> 36번방이 N으로 들어오면 출력은 4 입니다.


2. 풀이 과정


방의 갯수를 잘보면


1개 - [1]

6개 - [2~7]

12개  - [8~19]

18개 - [20~37]

24개 - [38~61]

32개

.

.

.

6 * 겹겹이 수


1, 6, 12, 18, 24 순으로 6의 배수로 한겹씩 둘러 쌓여지게 됩니다.

겹겹이 쌓이는 숫자와 1 에서 접근할 수 있는 개수의 최소값이 "같음"을 알 수 있습니다.


1 = 1칸

2~7 = 2칸

8~19 = 3칸

20~37 = 4칸 

.

.

.

이 방법을 이용하여 코드를 작성 하면 됩니다.


3. 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
 
using namespace std;
 
int main(void){
    //입력
    long long n;
    cin >> n;
 
 
    //계산
    int cnt = 1;        //몇겹인지 = 최소 칸수
    long long range =1//숫자의 범위 ex) 2~7, 8~19를 나타내기 위함
    long long tmp =1;   //6의 배수를 더하기 위해서 사용
 
    
    while(1){
        if(range >= n){ //숫자의 범위가 커지면 break;
            break;
        }
        tmp = 6 * (cnt++);
        range += tmp;
    }
 
    //출력
    cout << cnt;
    
    return 0;
}
 
cs


4. 인증


문제 출처 - https://www.acmicpc.net/problem/2292

감사합니다. 하트 버튼 꾹 부탁드립니다.



반응형