문제

' 8320번 직사각형을 만드는 방법 '
https://www.acmicpc.net/problem/8320

힌트

풀이

조건

• 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 없으면, 두 직사각형은 다르다고 한다.
• 직사각형은 정사각형으로 꽉 차있어야 한다.
• 첫째 줄에 n (1 ≤ n ≤ 10,000)이 주어졌을 때 만들 수 있는 직사각형의 개수를 출력한다.

Check point

• 가로가 x 인 경우 세로는 N//x 까지 가능하다.
• x*y 직사각형과 y*x 직사각형은 같은 경우로 보기에 중복되지 않도록 범위설정이 필요하다.

코드

Python

N=int(input())
total=0  # 직사각형 갯수
for i in range(1,N+1): #가로 영역 1~N
    for j in range(i, N//i+1): # 세로 영역 1~N//i인데 겹치는 경우 제외를 위해 i~N//i 까지 지정
        total+=1

print(total)

다른 방법

• 직사각형: 너비 x 높이 = 크기 (정사각형 소비) <= 정사각형 갯수
• i= 1 -> 1 ~ 6 / 2 -> 3~1 / 3 -> 2~ 1/ 4~6->1 / 정사각형 경우 +2 => 전체 합 16 => /2 = 8

N=int(input())
cnt=0
#(너비 x 높이) <= N 작은 값을 카운트
for W in range(1,N+1):
    mx_h = N // W  # 최대 높이값 계산
    cnt+=mx_h  # 1~최대값 범위를 cnt 누적

#정사각형 형태의 직사각형(w*w)
for w in range(1,N+1):
    if w * w <= N:
        cnt += 1

print(cnt//2)