BOJ 8320 - 직사각형을 만드는 방법

문제

N개의 정사각형 타일로 만들 수 있는 서로 다른 직사각형의 수를 구하라. i x j와 j x i는 같은 직사각형이다.

입력

첫째 줄에 정수 N (10,000 이하)이 주어진다.

출력

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

예제

입력	출력
`6`	`8`

풀이

모든 가능한 (i, j) 쌍을 탐색하여, i*j가 N 이하이고 i가 j 이하인 직사각형의 수를 센다.

i를 1부터 N까지 반복한다
j를 i부터 N까지 반복하며 i*j가 N 이하인 경우를 센다
i*j가 N을 초과하면 내부 루프를 종료한다

핵심 아이디어: i가 j 이하인 경우만 세므로 (i, j)와 (j, i) 중복이 자동으로 제거된다. 예를 들어 N=6이면 1x1, 1x2, ..., 1x6, 2x2, 2x3 총 8가지이다.

코드

package com.ssafy.an.day049;
 
import java.util.Scanner;
 
public class Day09BOJ8320직사각형 { // 8320
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int cnt = 0;
		for (int i = 1; i <= N; i++) {// 입력값이 6이라면 1~6까지 가능
			for (int j = i; j <= N; j++) {
				if (i * j <= N)
					cnt++;
			}
		}
		System.out.println(cnt);
		sc.close();
	}
}

복잡도

시간: O(N * sqrt(N)) — i가 커지면 j 범위가 빠르게 줄어듦
공간: O(1) — 상수 공간

문제