백준 2858 : 기숙사 바닥

백준 2858 : 기숙사바닥

---

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

[출처] ~2/11 두번째 스터디 문제 (비공개 카페)

기숙사 바닥 성공 풀이

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	740	419	355	60.477%

문제

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

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

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

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

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

입력

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

출력

첫째 줄에 상근이네 방의 크기 L과 W을 공백으로 구분하여 출력한다. 만약, 두 수가 다르다면, 큰 수가 L이 되고 작은 수가 W이 된다. 항상 정답이 유일한 경우만 입력으로 주어진다.

예제 입력 

10 2

예제 출력 

4 3

풀이

문제를 정리하면 다음과 같다.

- 빨간블럭 r개와 갈색블럭 b개가 있다.

- 모든 블럭은 1x1 크기이다.

- 안쪽에 갈색블럭이 b개가 모여 직사각형을 이루고 있고, 그 외부를 빨간블럭 r개가 감싸고 있다.

- 이때 합쳐진 전체 블럭(b+r)의 가로 W 와 세로 L 의 길이를 큰 순서로 출력하는 것이 문제이다.

처음에 빨간블럭과 갈색블럭이 주어지고,

중앙에 b개의 갈색블럭이 모인 형태(1*b, 2*(b/2), 3*(b/3) ...)에 따라 외부 빨간블럭의 개수 r이 정해진다.

따라서 b개의 갈색블럭 형태(가로, 세로 길이)를 찾는 것이 우선이다.

1. 빨간블럭 r, 갈색블럭 b 를 입력받는다.

2. 갈색블럭 b개가 모여 이루는 직사각형의 가로를 w, 세로를 l 이라 하면, l == b/w 이다.

3. 그러면 갈색블럭의 외부를 빨간블럭이 감싸야하므로 r == (w+2) * 2 + (b/w+2) * 2 - 4 을 만족해야한다.

    정리하면, r == 2*w + 2*b/w + 4

4. (3)의 식이 만족하면, W == w+2, L == l+2 인 W, L을 출력한다.

Java 소스코드 (b2858.class)

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        
        int r_brick = s.nextInt();
        int b_brick = s.nextInt();
        
        int l, w;
        
        for(l = 1 ; ; l++) {
            
            if(b_brick % l == 0) {
                w = b_brick / l;
 
                if(l*2 + w*2 + 4 == r_brick) {
                    System.out.println((w+2) + " " + (l+2));
                    break;
                }
            }
        }
    }
}

결과

자바언어는 비교적 연산 시간이 오래걸린다

동일한 알고리즘으로 C로 작성했더니 시간이 절반으로 단축되더라