[BOJ](Python) 8320번 : 직사각형을 만드는 방법

www.acmicpc.net/problem/8320

8320번: 직사각형을 만드는 방법

소스 코드는 다음과 같다.

import sys
input = sys.stdin.readline
T  = int(input())
square = 0
for i in range(1, T+1):
    check = []
    for j in range(2, i//2+1):
        if i % j == 0:
            if j in check:
                break
            else:
                square += 1
                check.append(i//j)
    square += 1
print(square)

먼저 2개 일 때의 경우, 그림과 같이 1X2만 가능함을 알 수 있다.

2개 일 때

3개 일 때, 2개와 마찬가지로 1X3만 가능하다.

반면, 4개일 때 1X4도 가능하지만 2X2도 가능하다.

4개 일 때

5개 일 때, 1X5만 가능하고, 6개 일 땐, 1X6, 2X3(3X2도 같지만 문제에선 두개는 하나로 취급한다.).

9개 일 땐, 1X9, 3X3이 가능하다.

 

종합하면, 임의의 n에 대해서 임의의 k로 나눌수 있을 때, 1 X n을 제외한 (n//k) * k도 가능하다.

k는 1보다 크고 n보다 작아야 하지만, n//2보다 크게 되면 6의 경우 2X3도 가능하지만 3X2도 가능해지면서 두개의 경우의 수가 생긴다. 따라서 k는 1보다 크고 n//2보다 같거나 작도록 설정하면 된다.

#정답 코드
for i in range(1, T+1):
    check = []
    for j in range(2, i//2+1):
        if i % j == 0:
            if j in check:
                break
            else:
                square += 1
                check.append(i//j)
    square += 1

하지만 n=4의 경우 2X2의 경우의 수도 포함할 수 있도록 해야하는데,

#실패 코드
for i in range(1, T+1):
    check = []
    for j in range(2, i//2+1):
        if i % j == 0:
            square += 1
            check.append(i//j)
    square += 1

실패 코드와 같이 설정을 하게 될 경우 n=4에서 2X2를 포함시킬 수 있지만 n=12에서 6X2를 포함하게 되버린다.

따라서 이를 방지하기 위하여 정답 코드와 같이 n=4에서 2X2를 포함시킬 수 있도록 하였지만, n=12에서 2X6를 포함했을 때, 6을 리스트에 넣어 6X2를 계산하려고 할 때 check list에서 6이 있으면 6X2를 추가시키지 않도록 설정하였다.

 

---

또 다른 풀이:

먼저 n=9일 때 임의의 k에 대해서 1Xk로 만들 수 있는 경우의 수는 9가지이다.

이를 표현하면 1~(9//1)개이다.

 

또한, 임의의 k에 대해서 2*k로 만들 수 있는 경우의 수는 3가지 이다. 2X2, 2X3, 2X4가 가능한데 이를 범위로 표현하면 2~(9//2) == 2~4 까지이다.

같은 방식으로 3Xk로 만들 수 있는 경우의 수는 1가지이다.

이를 범위로 표현하면 3~(9//3) 이다.

이를 종합하면, 임의의 n에 대해서 세로가 1인 경우의 수는 1~n//1개, 세로가 2인 경우의 수는 2~n//2개, 세로가 k인 경우의 수는 k~n//k개 이다.

 

이를 코드로 종합하면 다음과 같다.

n=int(input())
r=0
for i in range(1,n+1):
    for j in range(i,n//i+1):
        r+=1
print(r)

#출처: https://www.acmicpc.net/source/21455168, yooshnn