[BAEKJOON] 2292 벌집

문제

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

입력

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

출력

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

예제 입력 1 복사

13

예제 출력 1 복사

3

 

---

오랜만에 문제 풀기

기사 시험을 준비하느라 그 동안 문제를 풀지 못했었다 (변명

 

아무튼 복귀 문제로 간단한 문제로 시작해보기

 

이 문제 같은 경우 패턴 문제라는 것을 파악 할 수 있었다.

근데 근래에 dfs, bfs 탐색 문제를 많이 풀어서 그런가 바로 dfs,bfs 문제인가? 싶었는데

생각해보니 패턴이 존재하고 그 리스트 범위를 만들 필요는 없어보였다.

 

그렇다 이 문제는 dp 로 풀 수 있는 문제였다.

 

1 (1) = 1
2,3,4,5,6,7 (6) = 2
8,9,10,11,12,13,14,15,16,17,18,19 (12) = 3
20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37 (18) = 4

 

라는 증가 규칙이 존재하다는 것이다.

 

import sys

def solution(n):

    if(n == 1):

        return n

    else:

        ads = 6

        end = 7

        ret = 2

        while not end >= n:

            ret += 1

            ads += 6

            end += ads

       

        return ret

a = int(sys.stdin.readline().strip())

print(solution(a))

끗