[BaekJoon] #2292 벌집 | 백준 파이썬(python) 풀이 및 접근방법

문제

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

 

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

 

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

 

---

접근

이번 문제는 수열에 대해 이해하고 있다면 해결하기 수월합니다. 수열은 단순하게 말하면 특정 규칙에 의해 나열된 수을 의미하는데 [1, 2, 3] 도 수열일 수 있고 [1, 3, 5, 7, 9] 도 수열일 수 있으며 [1, 3, 7, 13] 도 수열일 수 있습니다. 흔히 반배치 고사를 볼 때나 인적성평가를 볼 때 "? 에 들어갈 수는?"을 구하는 문제가 다들 수열을 이용하는 문제라고 보시면 됩니다.

 

문제에 주어진 벌집 사진을 보다보면 거리에 특정한 규칙이 있다는 걸 알 수 있습니다. 바로 동일한 행렬에 포함된 방은 1이라는 방에서 출발해 도착하는 거리가 동일하다는 것입니다. 위의 사진에서도 검은색 행렬에 포함된 방은 1칸 (풀이에선 2칸)만에 갈 수 있으며 노란색 행렬에 포함된 방은 2칸 (풀이에선 3칸)만에 갈 수 있습니다. 그리고 이러한 규칙을 다시 파악해 보면

 

• 1 : 1칸
• 2 ~ 7 : 2칸
• 8 ~ 19 : 3칸
• 20 ~ 37 : 4칸
• 38 ~ 61 : 5칸
• ...

이라는 리스트가 나오는 것을 보실 수 있습니다. 이 리스트에서도 마지막 수만 다시 빼오면 [1, 7, 19, 37, 61, ...] 입니다. 규칙이 보이시나요? 보이신다면 무척이나 똑똑하신 겁니다. 규칙이 보이지 않더라도 괜찮습니다. 제가 설명해 드릴테니깐요.

 

• 7 = 1 + (6 * 1)
• 19 = 7 + (6 * 2)
• 37 = 19 + (6 * 3)
• 61 = 37 + (6 * 4)

이제 규칙이 보이시죠? 간단하게 설명하자면 n번째 행렬을 지날수록 마지막 방의 번호는 6 * n 으로 늘어나는 수열입니다. 그럼 이제 주어진 방 번호가 몇 번째 행렬인지를 안다면 해결할 수 있겠죠?

 

---

풀이

n = int(input())
n_max = 7
n_add = 6
n_result = 2

while True:
    if n == 1:
        n_result = 1
        break
    
    if n <= n_max:
        break
    else:
        n_add += 6
        n_max += n_add
        n_result += 1
        
print(n_result)

풀이 코드는 위와 같습니다.

우선 방 번호를 n으로 입력받습니다. 그리고 마지막 방의 번호를 7로 더하는 값은 6으로 결과는 2로 선언합니다.

 

그뒤 while을 true로 하여 break가 나오기 전까지는 루프를 돌도록 합니다. 이때 n이 1이라면 즉 출발지라면 대입이 필요가 없기에 결과를 1로 재 선언 후 break를 선언토록 합니다. n이 1이 아니라면 즉 출발지가 아니라면 n이 마지막 방보다 앞에 있는 방이거나 같은 방인지 확인합니다. 만일 맞을 경우 멈추고 결과를 표시합니다. 아니라면 add 값에 행결을 하나 지났기에 6을 더하고 max 값에 add 값 만큼을 추가합니다. 또한 결과를 1 추가합니다. 이러한 과정을 반복하여 마지막 방보다 앞에 있거나 같은 방일 때의 거리를 표시하도록 합니다.

 

---

마무리

이번 문제는 수열을 알기만 한다면 구현을 그다지 어려운 문제가 아니었습니다. 하지만 수열을 모른다면 문제를 이해하는 단계에서부터 좌절할 수 있습니다. 즉 수학의 기본적인 개념을 이해해야 한다는 것입니다. 프로그래밍을 잘 하는 것도 좋지만 NYPC나 정보올림피아드 등에서 수상하고 싶다면 수학 선행을 열심히 하는 것도 중요하다고 생각이 됩니다. 프로그래밍과 수학은 가까운 사이니깐요. ㅎㅎ

 

본 문제의 출처는 백준과 ICPC 입니다.