[백준 7단계] 2292 벌집

🥕 [ 백준 2292 ] 벌집

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

2292번: 벌집

 

🍒 문제 분석

벌집 모양으로 인덱스가 주위를 빙글빙글 돌며 매겨진다고 한다.

인덱스 N 값은 1번 방으로 부터 최단거리로 몇 개의 방을 들러야 할까? 단, 1번 방과 N번방을 포함하여 센다.

예를 들어 3번 방은 2개, 26번방은 4개 이다.

 

🥑 코드

N = int(input())
n = 1
while True:
    S = 1+(6*(n-1)*n)//2     # 점화식 구해서 계산함
    if N <= S:
        break
    n +=1
print(n)

 

🍓 내 해결 과정

전형적인 군수열 문제인걸 알 수 있었다.

군의 갯수에 대한 점화식을 세우고자 숫자를 세봤다.

1군 :  1                                            # 1개

2군 : :2, 3, 4, 5, 6, 7                             # 6개

3군 : 8 ~ 19                                      # 12개

4군 : 20 ~ 37                                     # 18개

5군 : 38 ~ 61                                     # 24개

군수열 갯수에 대한 점화식 : \(a = 6*k-6\ 단,\ n=1일때\ a=1 \)

$$ 1+\Sigma^{k=n}_1(6*(k-1)) = 1 + 6*(n-1)*n/2 $$

 

n이 각 군에 해당 ( 또는 room의 갯수 )

각 군에 속한 인덱스 갯수의 합을 수열 a

수열 a의 합보다 인덱스 값이 더 작거나 같은 부분을 발견한다면,

그때의 군의 값이 곧 들르는 방의 숫자가 된다.

 

가령  11 의 경우 3군 까지의 수열 합 보다 더 작은 인덱스이고

따라서 11은 3군에 속하여, 방의 갯수는 3이다.

 

오랜만에 점화식 푸니 조금 헷깔리고 시간이 걸렸다.

 

 

🌽 다른 사람 코드

n = int(input())
room = 1
count = 1

while n > room:
    room += 6 * count
    count += 1
print(count)

팀원 분 코드를 참고했다.

 

count가 군에 해당하는 듯 하다.

room의 값을 다음과 같이 더해나가며 인덱스 값 n과 비교했다.

 

room = 1

room = 1+6

room = 1+6+12

...

 

room에 대한 연산 값은 내 수열 합에 대한 식과 같다.

room이 수열 합에 해당하는 것 같다.

 

점화식 계산하는 것 보다 이렇게 푸는게 더 빠르고 깔끔해 보였다.

 

 

🍉 깨달은 점 및 정리

 

간단하고 좋았다.

 

다만 유의할 점은, 가령 8군에 해당하는 8군 안의 인덱스 값은

8군까지의 합보다 늘 작다는 것을 기억해두자.