[백준/Java] 8320번 : 직사각형을 만드는 방법

[문제]

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

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

[조건]

• 시간 제한 : 1초
• 메모리 제한 : 256MB

[입력]

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

[출력]

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

[문제 풀이]

• 실제 블럭을 쌓는다는 것을 상상하며 풀이함
• 매번 블럭은 1개, 2개, 3개, .., N개가 한 세트임
• 1개의 블럭으로 만들 수 있는 직사각형은 N개 이므로 res=N으로 초기화
• 이후 2개의 블럭으로 만들 수 있는 경우를 상상하며, 2*1, 2*2 ~,,, 를 진행해 전체 개수인 N을 넘지 않을 때까지 진행
• N개 블럭까지 진행해 최종 답 구함

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int res = N;
		for (int i=2;i<=N;i++) {
				int idx = i;
				while (i*idx<=N) {
					res++;
					idx++;
			}
		}
		System.out.println(res);
	}
}

 

출처 : 백준 https://www.acmicpc.net/problem/8320