[백준/C] 2858번 기숙사 바닥

 

백준 온라인 저지 / 2858번 기숙사 바닥

https://www.acmicpc.net/problem/2858

2858번: 기숙사 바닥

 

• 사용언어 : C (C99)
• 알고리즘 : 수학, 브루트포스 알고리즘, 사칙연산

 

(문제 사진)

C 코드

1. 문제 정리

상근이의 기숙사 바닥은 빨간 타일과 갈색 타일로 이뤄져있는데, 친구 하근이가 상근이의 기숙사의 타일의 색 개수는 기억을 하지만 방의 사이즈가 생각이 나지 않아서 타일 색의 개수를 가지고 방의 사이즈를 알아내는 문제이다. 

범위: 빨간색 타일의 수 R과 갈색 타일의 수 B가 주어진다. (8 ≤ R ≤ 5000, 1 ≤ B ≤ 2,000,000)

 

2. 문제 접근하기

일단 바로 알 수 있는 점은 빨간 타일의 수 + 갈색 타일의 수 = 총 타일의 수라는 것이다.  이 문제를 풀 때 가장 중요한 조건이 방의 넓이 % 방 한 변의 길이 = 0  가 꼭 되어야만 총 넓이를 알 수 있다는 것이다. 이 조건을 만족하지 않는다면 직사각형이 아니라는 뜻이 된다.

예를 들어, 한 변의 길이가 7일 때 방 넓이가 12라면 성립 될 수 없는 식이다. 한 변의 길이를 1씩 더하면서 탐색 하며 방의 넓이가 될 수 있는 최적의 변의 길이를 찾으면 되는 문제이다. 

이제 갈색 타일의 크기를 구하기 위해 갈색의 세로와 가로를 구하려고 하는데, 먼저 브루트포스로 계속 1씩 더해가며, 변을 대입하면서 봐야하는 식을 보도록 하자

if((l-2) * (sum / l-2) == B)

먼저 L - 2를 보면, L이 3일 경우 1이 나오고 총합 / 1을 곱하면 갈색 부분의 세로 * 가로와 같은 식이 된다. 만약 아니라면 L이 4일 경우를 탐색, 5일 경우를 탐색 6 .. 7 .. 8. .. 이런 식으로 탐색하게 만드는 문을 브루트포스 알고리즘이라고 한다.

다음과 같은 식이 성립할 때 break 하도록 하여 문제를 해결하였다.

 

 

 

 

3. 완성 코드

#include <stdio.h>

int main(void){
	int R, B, sum = 0, l = 0 , w=0;
	
	scanf("%d %d", &R, &B);
	sum = R + B;	
	for(l = 2;; l++){
		if(sum % l == 0){
			if((l-2) * (sum / l-2) == B){
				w = sum / l;
				break;
			}
		}
	}
	
	if(w < l)
		printf("%d %d", l, w);
	else
		printf("%d %d", w, l);
	
}