[백준] 8320번 : 직사각형을 만드는 방법 - 자바(JAVA)

https://www.acmicpc.net/problem/8320

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

 

문제 해석

1 x 1 크기의 정사각형이 N개 존재합니다.

이 정사각형을 이용하여 만들 수 있는 직사각형을 개수를 구하세요.

 

 

문제 풀이 전 설계

반복문을 통해 i= 1 ~ N까지 반복합니다.

하나의 반복을 통해 i개 정사각형으로 만들 수 있는 직사각형의 개수를 구합니다.

 

우선 홀수/ 짝수로 나누어 생각해봤습니다.

홀수 1, 3, 5, 7, 9의 경우에는 한 줄로 밖에 가능하지 않을까 싶었지만 9의 경우에는 3/3/3으로 직사각형을 만들 수 있을 것 같습니다. ( 정사각형은 직사각형)

 

따라서 i가 자신보다 작은수로 나누어 떨어질 수 있는 수가 된다면 그만큼 직사각형의 개수를 만들 수 있다고 생각이 듭니다.

 

예를 들어

N = 4

1 을제 외하고 4보다 같거나 작은 수는 2, 3, 4입니다.

이때 2, 4로 나누어질 수 있고 4개의 정사각형을 통해서는 2개의 직사각형을 만들 수 있습니다.

 

N = 12

1을 제외하고 12보다 같거나 작은 수는 2,3,4,5,6,7,8,9,10,11,12입니다.

이때 2,3,4,6,12로 나누어질 수 있으며 12개의 정사각형을 통해서는 5개의 직사각형을 만들 수 있습니다.

 

이때 3,4는 회전했을 때 같은 직사각형이며  2,6또한 회전했을때 같은 직사각형입니다.

3 x 4 = 4 x 3이랑 동일한 느낌입니다.

따라서 약수의 개수를 구해야 하지만 절반까지만 구하면 될 것 같습니다.

 

이때 절반까지만 구하게 되면

 

N = 6일 때

1,2,3까지 구하게 되는데 2 x 3 = 3 x 2 이므로 반례가 발생합니다.

 

소수를 구하는 유명한 "에스토스테네스의 체"라는 알고리즘에서 소수를 구하기 위해 약수를 배제하는 방법으로 해당 수의 제곱근까지 구하는 방법이 떠올라서 그대로 적용하면 될 것 같습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main_8320_직사각형을만드는방법 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int rectCount = 0;
		for(int i=1; i<=N; i++) {
			if(i<=3) {
				rectCount++;
				continue;
			}
			
			for(int j=1; j<=Math.sqrt(i); j++) {
				if(i%j !=0) {
					continue;
				}
				rectCount++;								
			}			
		}
		System.out.println(rectCount);
	}

}