[백준] 2858번: 기숙사 바닥

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

2858번: 기숙사 바닥

 

 

 

코드

import java.util.Scanner;

public class Main {
	static final int max = 5000;
	static final int max2 = 4000;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int R = scan.nextInt();	// 빨강
		int B = scan.nextInt();	// 갈색
		int L = 0;
		int W = 0;

		for(int i=1; i<=max; i++) {
			for(int j=1; j<=max2; j++) {
				if(R+B == i*j) {
					if(R == (i*2) + (j-2)*2) {
						L = i;
						W = j;
						break;
					}
					else if(R == (j*2) + (i-2)*2) {
						L = j;
						W = i;
						break;
					}
				}
			}
		}

		System.out.println(L + " " + W);
		scan.close();
	}

}

 

풀이

나는 수학적으로 규칙을 찾아서 해결했다 ..

 

가로 = L, 세로 = W, 빨간색 = R, 갈색 = B라고 했을때,(L>W)

 

일단 첫번째 조건은 가로 * 세로 = 빨간색타일 + 갈색 타일이다.

1) L * W = R + B

 

가장 자리는 빨간색이므로, 빨간색 타일의 합은

윗변(L) + 아랫변(L) + (옆변-2)(W-2) + (옆변-2)(W-2) 이다.

위 사진에서, L = 4, W = 3이다.

하지만 각 꼭짓점의 면은 겹치므로 더할때 빼준다.

2) R = (L*2) + (W-2) * 2

 

 

1) L * W = R + B

2) R = (L*2) + (W-2) * 2

위 두 식을 그대로 적용했다..

 

1 <= B <= 2,000,000 이므로 i, j의 최댓값은 5,000 , 4,000 으로 잡았다.

 

1) i, j의 반복문을 통해 R+B = i*j 인 곳을 찾는다.

2) R+b = i*j 일때, R = (i*2) + (j-2) *2 인 곳을 찾는다.

3) L이 W보다 크므로, R = (i*2) + (j-2) *2 일땐 L의 값이 i, W의 값이 j가되고 반대로는 반대값이다.