[백준] 2292. 벌집

2292번: 벌집

---

이 문제는 총 3번 시도했다.
1차 시도는 재귀함수로 풀었다가, RecursionError가 났고
2차 시도는 시간오류라고 표시됐는데, 다시 뜯어보니 아예 잘못 짠 거였다.
그렇게 3차 시도에서 통과했다.

우선, 1차 시도는 이렇게 재귀 함수로 짜보았다.
예시 입출력은 통과했는데, Recursion Error가 나버렸다.

# 2292 벌집
# 규칙성을 따져보면 벌집의 숫자는 6의 배수로 늘어난다.
# 가령 1은 6의 0제곱, 1을 둘러싼 원은 2-7(6개), 그 다음 원은 8-19(12개), 다음 원은 20-37(18개)...
# 이걸 레벨별로 정리하면, level 1은 6의 0제곱, 2레벨은 1레벨 + 6 * 1 범위 내, 3레벨은 2레벨 + 6* 2의 범위 내
# 재귀 함수로 만들어놓고 나중에 return 값으로 cnt를 받으니까 None이 떠서 왜이러지 한참 고민했다
# 1레벨로 다시 돌아왔을 때 return 값이 없으니까!!

def find_loc(start, cnt):
    global ret_cnt
    for i in range(1, 6 * cnt + 1):
        if start + i == N:
            ret_cnt = cnt
            return
        if i == 6 * cnt:
            start += i

    find_loc(start, cnt + 1)
    return


N = int(input())
ret_cnt = 0
if N == 1:
    print(1)
else:
    find_loc(1, 1)
    print(ret_cnt+1)

그래서 재귀함수 대신, 반복문을 활용해보기로 했다.
그랬더니 시간 오류가 났는데, 자세히 보니 (6 * i) + 1이랑 비교하면 안되고, 이전의 값에 (6 * i)을 더한 값으로 비교를 했어야 했다. 아마 그렇게 안해서 너무 작은 수랑 비교하게 되어서 시간오류가 났던 것 같다.

# 근데 이렇게 풀었더니 RecursionError가 나왔다.
# RecursionError는 최대 재귀 깊이를 넘었을 때 발생하는 현상이다.
# 레벨의 마지막 값들이 1, 7, 19, 37...인데 이 수들은 전부 -1 하면 6*0, 6*1, 6*2...이다.
# 즉 들어온 수 n이 6 * ? -1 이하일 때 이 ?가 뭔지만 확인하면 된다.

n = int(input())
i = 0
while (6 * i) + 1 <= n:
    i += 1

print(i)

그렇게 final_room_num이라는 각 방 넘버의 마지막 수들(1, 7, 19, 37..)에 (6 * cnt)가 더해지는 식으로 짠 후, cnt + 1 한 값을 1에서 N번까지 갈 수 있는 최소거리로 출력해줬다. 말끔하게 통과~!

# (6 * i)가 곧 각 층의 마지막 수가 아니라
# 마지막 수에 계속 더해지는 식으로 짰다.

n = int(input())
cnt = 0
final_room_num = 1
while n > final_room_num:
    cnt += 1
    final_room_num += 6 * cnt

print(cnt + 1)