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

문제 분석

- 규칙을 찾으면 풀 수 있다.

 

 

문제 풀이

1) 높이가 1부터 제곱해서 n이 되는 수까지 경우의 수를 구한다.

2) 각 높이가 정해졌을 때 가로의 길이를 해당 높이부터 n까지 계산해본다(cf. n까지 가다가 제곱한 수가 n을 넘으면 더이상 계산할 필요가 없다)

 

예시)

16일 때,

높이가 1 : 1, 2, 3, 4, 5, ... ,15,16

높이가 2 : 2, 3, 4, 5, 6, 7, 8

높이가 3 : 3, 4, 5

높이가 4 : 4

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int n, ans;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());

		recursive(1); 
		System.out.println(ans);

	}// main

	private static void recursive(int c) {
		if (n / c < c) {
			if (n / c == c)
				ans++;

			return;
		}

		for (int i = c; i <= n; i++) {
			if (c * i <= n)
				ans++;
			else
				break;

		}

		recursive(c + 1);
	}

}// class-end