[Baekjoon] 2589 기숙사 바닥

알고리즘 분류

수학

브루트 포스

 

문제 - https://www.acmicpc.net/problem/2858

 

-문제-

상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다.

수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이때, 가장자리는 빨간색으로, 나머지는 갈색으로 채우려고 한다.

아래 그림은 상근이의 방의 크기가 4*3일 때 이다.

어느날 상근이네 방에 하근이가 놀러왔다. 하근이는 아름다운 타일 배치에 감동받았다. 다시 방으로 돌아온 하근이는 빨간색과 갈색 타일의 개수는 기억했지만, 방의 크기는 기억해내지 못했다.

빨간색과 갈색 타일의 개수가 주어졌을 때, 상근이 방의 크기를 구하는 프로그램을 작성하시오.

 

-입력조건-

첫째 줄에 빨간색 타일의 수 R과 갈색 타일의 수 B가 주어진다. (8 ≤ R ≤ 5000, 1 ≤ B ≤ 2,000,000)

 

-해결방법-

1. 행의 숫자를 1씩 높여가며 갈색 타일의 숫자 를 나눠준다. (ex. B= 6일때, 6/1(행의 숫자) = 6(열의 숫자))

2. 나머지가 없을때, 열과 행의 숫자에 2씩 더한뒤 곱한다.

3. 2에서 나온 수에서 갈색타일의 숫자를 뺀뒤 빨간색 타일의 수와 비교한다.

4. 같으면 종료, 같지 않으면 1.으로 다시 돌아가서 실행

 

<소스코드>

#include <iostream>
using namespace std;

int main()
{
	int L, W;
	cin >> L >> W;
	int i = 1;
	int j;
	while (1) {
		if (W%i != 0) {
			i++;
		}
		else {
			j = W / i;
			int temp = (j + 2)*(i + 2);
			temp -= W;
			if (temp == L) {
				if ((j + 2) > (i + 2))
					cout << j + 2 << " " << i + 2 << endl;
				else
					cout << i + 2 << " " << j + 2 << endl;
				break;
			}
			i++;
		}
	}
	
    return 0;
}