BOJ 2858 - 기숙사 바닥

문제

테두리의 빨간 타일 R개와 내부의 갈색 타일 B개가 주어질 때, 바닥의 가로 세로 크기를 구하라.

입력

빨간 타일 수 R과 갈색 타일 수 B가 주어진다.

출력

가로와 세로를 공백으로 구분하여 출력한다 (가로 >= 세로).

예제

입력	출력
`24 24`	`8 6`

풀이

둘레와 넓이 관계를 이용하여 가로 세로를 역산한다.

L + W = (R + 4) / 2 (둘레 관계)
L * W = R + B (넓이 관계)
1부터 순회하며 두 조건을 동시에 만족하는 해를 찾는다

핵심 아이디어: 테두리 타일 수에서 둘레를, 전체 타일 수에서 넓이를 도출하여 2차 방정식으로 풀 수 있다.

코드

R, B = map(int, input().split())
LpW = (R + 4) // 2
LW = R + B
 
for i in range(1, LpW):
    if (LpW - i) * i == LW:
        print(max(i, LpW - i), min(i, LpW - i))
        break

복잡도

시간: O(N²)
공간: O(N)

문제