Algorithm/문제풀이
[C++] 백준 알고리즘 2858 기숙사 바닥
사과당근
2021. 9. 27. 02:43
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';
}