[백준 알고리즘/python] 백준 2292번 벌집, 파이썬

백준 알고리즘 2292번 벌집, 파이썬

 

이번 문제는 백준 알고리즘의 2292번 벌집 문제이다.

역시 파이썬으로 풀어보았다.

 

문제 이해를 잘 해보면 방 1을 1개로 치고 그 번호가 매겨져 있는 방까지 문을 몇번 열어야 갈 수 있냐는 문제이다.

잘 보면 중심에있는 1번방은 하나, 2번부터 7번까진 두개, 8번부터 19번까진 3개이다.

이걸 수열로 정리해보면

1 7 19 37 61....

이런식이다.

 

고등학교때 배웠던 "계차수열"이 떠오른다.

무슨 수열 형탠지는 알겠는데, 계차수열의 일반항을 구하는 식이 생각나지 않아서 검색 해 봤다.

 

결론은

An = A1 + Bn(n = 1 부터 n = k-1)까지의 합이다.

나는 수학 설명을 하는 재능은 딱히 없으니, 더 궁금하면 찾아보도록 하자.

이 식을 통해 위 문제를 점화식으로 적어보면

 

An = 3n^2 - 3n +1 로 형태가 나온다.

1을 넣으면 1, 2를 넣으면 7 3을 넣으면 19가 나오므로 검산해봐도 맞게 나온다.

 

자, 그럼 이제 문제에 대한 내 생각이다.

# 생각 1. 일반항을 구했으니 반복문을 통해 1부터 수열을 올리기 시작한다.

# 생각 2. 반복문 한번이 돌아가면 방의 개수도 하나씩 올라간다.

# 생각 3. an과 an+1 사이에 입력값이 존재하면 중단하고 개수를 반환한다.

# 생각 4. 1이 주어지면 그냥 1을 반환하고 멈추는게 생각하기 편할것같다.

 

나는 위처럼 생각하고 아래처럼 코드를 썼다.

room = int(input())
count = 2

i = 1
while True:
    if room == 1:
        print("1")
        break
    if room  >=(3*i*i-3*i+1) and room <= (3*(i+1)*(i+1)- 3*(i+1)+1):
        print(count)
        break
    else:
        count = count + 1
    i = i + 1

 

보면 알겠지만 간단하다.

무한루프를 돌리면서 1씩 증가시키고, 그 다음항과의 범위 안에 입력값이 들어와있으면 반환한다.

그 뿐이다.

 

솔직히 이 문제는 점화식을 구하는데 시간이 오래걸렸지, 코드는 금방 짜 내려갔던거 같다.

 

문제 출처

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

2292번: 벌집