Python 백준 8320번 - 직사각형을 만드는 방법 (시간 초과 해결)

문제

상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까?

두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 없으면, 두 직사각형은 다르다고 한다. 직사각형을 만들 때, 정사각형을 변형시키거나, 한 정사각형 위에 다른 정사각형을 놓을 수 없다. 또, 직사각형은 정사각형으로 꽉 차있어야 한다.

N 이 6일때 만들 수 있는 직사각형들

입력

첫째 줄에 n (1 ≤ n ≤ 10,000)이 주어진다.

출력

만들 수 있는 직사각형의 개수를 출력한다.

 

나의 생각

처음에 1부터 8개 정도까지 그려보면서 어떤 경우가 될 수 있는지 확인을 해보았다. 우선 세로 로긴 직사각형은 일정하게 증가한다는 것을 알아내었고, 특별한 경우에만 개수가 더 증가한다는 것을 알았다. 예를 들면, 4에서는 정사각형을 만들 수 있고, 8,10 에서는 가로가 2인 직사각형을 추가로 만들 수 있었다. 그래서 생각한 알고리즘은 1부터 증가하면서 각각의 약수들을 구하고 풀면 될 것 같다고 생각이 들었다. 

ex) N = 6 일때  1부터 6까지 가로 1짜리 6개를 만들 수 있고, 나머지는 약수인 2,3의 경우와 이전 N = 4일 때의 경우가 더해져서 총 8개가 만들어진다. N = 4일 때를 말한 것은 for 문이 돌면서 이전에 값을 중첩하기 때문이다. 코드를 보면 알 것이다.

 

코드 1

import sys, math
N = int(sys.stdin.readline().rstrip())
result: int = 0 
divisor: list = []
if N == 1: print(1)
else:
    for i in range(1, N+1):
        for j in range(1, i+1):
            if i % j == 0:
                divisor.append(j)
        result += math.ceil(len(divisor) / 2)
        divisor.clear()
    print(result)

결과

역시 내가 예상한 대로 시간 초과가 나왔다. 콘솔에도 최댓값인 10000을 입력하면 1초가 넘어갔다. 그래서 다른 알고리즘을 생각해 보았다.

 

코드 2

완전 다르게 생각하였다. 넓이 개념으로 생각을 했다. 우선 N=6이라는 것은 1*1짜리 6개가 있기 때문에 넓이가 6을 넘지는 않을 것이다. 그리고 for 문을 2개를 썼는데, 하나는 가로 하나는 세로로 보면 이해가 편할 것이다. 여기서도 시간 초과의 함정이 존재하는데 어떤 것일까, 바로 else: break 저부분이다. 저 break 가 없어도 결과는 동일하지만 시간 효율이 굉장히 떨어진다. 그래서 해당하지 않은 경우는 바로 반복문을 빠져나가는 것이 좋다.

import sys
N = int(sys.stdin.readline().rstrip())
result: int = 0
for i in range(1, N+1):
    for j in range(1, i+1):
        if i * j <= N: result+=1
        else: break
print(result)

 

결과