[C++] 백준 알고리즘 2858 기숙사 바닥

1. 테두리가 성립하는 모든 경우의 수를 구한다.

2. 해당 테두리로 사각형을 만들었을 때, 입력한 안쪽 벽돌의 갯수가, 만들어진 사각형의 내부 갯수와 같은지 확인한다.

 

테두리를 구하는 방법은,

가로길이 * 2 + 세로길이 *2 를 한 다음 겹치는 모서리 4개를 빼줘도 된다.

나는 가로길이 *2 + (세로길이-2) * 2 를 했다.

 

i = 가로

j = 세로 인데,

가로의 범위와 세로의 범위는 주석에 적어뒀다.

#include<iostream>

using namespace std;

int main() {
	int r, b;
	cin >> r >> b;
	
	int l, w;
	//i의 범위
	// 세로 길이가 가장 짧은게 3이다.
	// 이 경우 가로와 겹치지 않은 세로 벽돌은 2개 뿐임.
	//따라서 2개를 빼주고 위와 아래 2개가 있으니 나누기 2
	for (int i = 3; i <= (r-2) / 2; i++) {
		//j의 범위
		//= 전체  테두리 - 위 아래 테두리 (i*2) + i에서 빼버린 왼쪽 오른쪽 테두리 끝 (+4)
		//위의 것을 왼쪽과 오른쪽이 존재하므로 나누기 2
		for (int j = 3; j <= (r - i * 2 + 4) / 2; j++) {
			//전체 - 테두리 == 안쪽 벽돌 갯수일 때
			if (i * j - (i * 2 + (j - 2) * 2) == b) {
				if (i * 2 + (j - 2) * 2 == r) {
					if (i < j) {
						l = j;
						w = i;
					}
					else {
						l = i;
						w = j;
					}
					break;
				}
			}
		}
	}
	cout << l << ' ' << w << '\n';
}