백준 8320번 직사각형을 만드는 방법 파이썬

리뷰

처음엔 조금 막막했으나 알고리즘 분류가 수학인 만큼 점화식이 있을 거라고 생각했고 규칙을 찾아낸 후엔 문제를 쉽게 풀 수 있었다.

문제 풀이

n	1	2	3	4	5	6	7	8	9	10	11	12	13
result	1	2	3	5	6	8	9	11	13	15	16	19	20

1부터 13까지의 수를 대입해 보았을때 처음엔 피보나치 수열인가? 생각했으나 별다른 규칙성을 찾지 못했다. 그래서 노가다를 시작했다.

n	■	■■	■■■	■■■■	■■■■■	■■■■■■	■■■■■■■	■■■■■■■■	■■■■■■■■■
n // 2 - 1	■■ ■■	■■■ ■■■	■■■■ ■■■■
n // 3 - 2	■■■ ■■■ ■■■

위의 표는 N이 9일때의 직사각형을 만들 수 있는 경우의 수이다. N이 4일때와 9일때 새로운 모습의 정사각형을 만들 수 있다는 것을 깨닫고 위와 같은 점화식을 세울 수 있게 되었다.

참고 사항

N이 최대 10000까지 입력 가능한 점을 염두해 두면 좋을 것 같다. 나는 for문의 범위를 100까지로 한정지어 틀렸습니다가 노출되었었다.

range의 최대값을 101로 고정하지 않고 math를 import해주고 sqrt를 이용해 주거나 int(n ** 1/2))를 통해 최대값을 지정해 준다면 더 최적화된 코드가 완성될 것 같다. 나는 어차피 시간 초과가 나지 않을 것이니 그냥 101로 넣어주었다.

정답 코드

def q8320():
    # 백준 8320번 직사각형을 만드는 방법 파이썬
    n = int(input())
    result = n
    for i in range(2, 101):
        result += max(0, n // i - (i - 1))
    print(result)
q8320()