백준 8320. 직사각형을 만드는 방법

[문제]

유형: 수학/구현

언어: C++

난이도: 브2

사이트: https://www.acmicpc.net/problem/8320

---

[리뷰]

쟁점: 넓이가 n을 넘지 않으면 된다. 시간 제한 1초인데 N은 10,000까지이므로 시간복잡도에 따라 최대 이중 반복문까지 가능하다.

틀렸던 문제.

두 변의 길이를 곱해서 n을 넘지 않으면 된다.

즉, 두 숫자의 조합을 구하면 되는 문제이며, 당연히 숫자의 범위는 n까지 가능하다(직사각형 1 * n 크기).

이동/회전은 의미가 없으므로, 순열이 아닌 조합으로 생각하면 이해하기 수월하다. nC2

 

학습 내용.

none

 

오답 노트.

처음엔 약수를 구하면 된다고 생각했다. 단순히 약수 개수를 구하니, 중복을 제거하기가 까다로웠다. 게다가, 시간 초과.

그저 단순히 두 개의 숫자를 곱했을 때, n을 넘지 않으면 되는 거였다.

 

해답.

이중 반복문.

for i (1, n)

    for j (i, n)

        i * j > n 가 아닐 때에만 조건 해당

설명 1. j의 범위가 (1, n)이 아닌 (i, n)인 이유는 중복 때문이다. (중복 제거)

설명 2. i * j > n 일 때, 반복문 종료는 불필요한 연산을 없애기 위함이다. (하단 코드 참조)

 

[코드]

// p8320. 직사각형을 만드는 방법
// C++로 다시 풀기
#pragma warning(disable:4996)
#include<iostream>
using namespace std;

int main(void)
{
	int n, ans = 0;
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; ++j)
		{
			if (i * j > n)	break;
			ans++;
		}
	}
	cout << ans;

	return 0;
}