백준 BaekJoon Online Judge // 2292

백준 알고리즘 BaekJoon Online Judge 2292번 "벌집" 문제입니다.

N = int(input())
for i in range(0, 200000000):
  if N == 1:
    print(N)
    break
  if N <= 3*i*i - 3*i + 1:
    print(i)
    break

현재 백준 수학파트 문제를 다루고 있어서 그런지 수학적 지식을 사용하는 문제가 많이 나온다.

 

벌집 문제

위처럼 방마다 숫자가 매겨진 벌집 모양의 그림이 있다. N이 입력되었을 때 1부터 출발하여 N 번째 방까지 몇 개의 방을 지나가는지 구하는 문제다.

 

1부터 시작하여 1을 둘러싸는 껍데기를 구성하는 방의 수가 점점 늘어나는 것을 알 수 있다.

 

둘러 쌓이는 껍데기층이 많아질수록 1부터 시작하면 1 -> 7 -> 19 -> 37...로 개수가 늘어나는 것을 확인할 수 있다.

 

얼핏 보면 저 수들에서는 규칙성이 없어보이지만 저 수열에서 각각 수들의 차를 써보면

 

7-1 = 6, 19-7 = 12, 37-19 = 18 => 6, 12, 18...로 쓸 수 있다.

 

6, 12, 18은 6을 시작항으로 하고 6씩 늘어나는 등차수열의 성질을 띤다.

 

따라서 본 수열은 계차수열이라는 것을 알 수 있다.

 

계차수열에 관한 정보는 아래에 링크해두겠다.

 

namu.wiki/w/%EA%B3%84%EC%B0%A8%EC%88%98%EC%97%B4

계차수열 - 나무위키

따라서 원래 수열의 일반항은 6*(n-1)*n / 2 + 1 = 3*n*(n-1) + 1 = 3n^2 - 3n + 1이다.

 

따라서 입력받은 N의 값을 위의 식과 for 반복문, 조건문을 활용하면 방을 얼마나 지나는지 알 수 있다.

 

다만 1의 경우는 따로 예외로 둬서 1을 따로 출력하는 방식을 사용하였다.