백준 2292번 벌집
문제
육각형 방으로 이루어진 벌집의 중앙이 1번이고, 이웃한 방으로 돌아 나가며 번호가 1씩 커진다. N(1 이상 1,000,000,000 이하)이 주어지면 1번에서 N번 방까지 최소 개수의 방을 지나서 갈 때 지나는 방의 수(시작과 끝 포함)를 출력한다. 예를 들어 13번까지는 3개, 58번까지는 5개다.
풀이
겹마다 방의 개수가 6, 12, 18, 24로 6씩 늘어난다. 각 겹의 첫 번호를 늘어놓으면 1, 2, 8, 20, 38, 62이고 그 차이는 1, 6, 12, 18, 24다.
처음에는 이 수열의 일반항을 구해 N에서 거꾸로 겹의 수를 계산하려 했다. 식은 겹의 수를 넣으면 번호가 나오는 방향이라 거꾸로 풀기가 어려웠고 시간만 허비했다. 그래서 방향을 바꿔 while문으로 겹을 하나씩 늘려 가는 방법을 썼다. 시간 초과가 날까 봐 처음에는 반복을 피했지만, 겹의 수가 수만 단위로 끝나서 문제가 없었다.
a는 현재 겹의 마지막 번호이고 cnt는 지나는 방의 수다. a가 N 이상이 될 때까지 다음 겹의 방 개수 6 * cnt를 더하며 cnt를 1씩 올린다.
num = int(input())
a = 1
cnt = 1
while num > a:
a += 6 * cnt
cnt +=1
print(cnt)짚고 갈 점
- 이 수열은 항 사이의 차이가 6씩 늘어나는 계차수열이다. 원글에서는 등비수열이라 불렀지만, 비율이 아니라 차이가 일정하게 커지므로 등비수열이 아니다.
- 식으로 풀다가 막히면 단순한 반복으로 돌려 보는 편이 빠를 때가 있다.