[Algorithm] 백준 8320 직사각형을 만드는 방법

[ 문제 ]

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

 

두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 없으면, 두 직사각형은 다르다고 한다.

직사각형을 만들 때, 정사각형을 변형시키거나, 한 정사각형 위에 다른 정사각형을 놓을 수 없다.

또, 직사각형은 정사각형으로 꽉 차있어야 한다.

 

[ 입력 ]

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

 

[ 출력 ]

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

 

[ 예제 입력 ]

6

 

[ 예제 출력 ]

8

 

---

예를 들어 8개로 만들 수 있는 직사각형은

가로 길이 : 1, 세로 길이 : 8

가로 길이 : 2, 세로 길이 : 4

가로 길이 : 4, 세로 길이 : 2

가로 길이 : 8, 세로 길이 : 1

입니다.

 

하지만 문제에서 회전했을 때 같다면 한가지 경우로 친다고 했기 때문에

가로 길이 : 1, 세로 길이 : 8인 경우와 가로 길이 : 8, 세로 길이 : 1인 경우는 같은 경우입니다.

 

따라서 총 count에서 2로 나누어주었습니다.

 

import java.io.*;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()); // 가지고 있는 정사각형 개수
		
		int count = 0;
		for (int i = 1; i <= n; i++) {
			if (i <= 3)	count += 1;  // 1개, 2개, 3개로 만들 수 있는 직사각형은 각각 1개
			else {
				int temp = 0;
				for (int j = i; j > 0; j--)
					if (i % j == 0)	temp += 1;
				count += (temp + 1) / 2;
			}
		}
		
		System.out.println(count);
	}
}