[Lv2] 카펫

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

 

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 빨간색으로 칠해져 있고 모서리는 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 빨간색 격자의 수 red는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

입출력 예

brownredreturn

brown	red	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

문제 원출처: http://hsin.hr/coci/archive/2010_2011/contest4_tasks.pdf

 

---

 

카펫은 정사각형이거나, 가로가 긴 직사각형임. (직사각형이더라도 가로가 얼마나 더 길어야 하는 제한은 없음)

 

중앙은 모두 빨간색이고, 빨간색을 1칸 두께로 갈색이 둘러싸고 있음.

 

빨간색은 1 이상 2,000,000 이하임.

 

public int[] solution(int brown, int red) {
    boolean isSame = false;
    int redwidth = 0;
    for(int i=1;i*i<=2000000;i++) {
        if(red==i*i) {
            isSame = true;
            redwidth = i;
            break;
        }
    }
    if(isSame) {
        return new int[] {redwidth+2,redwidth+2};
    } else {
        int redheight = 0;
        for(int i=1;i<=2000000;i++) {
            for(int j=1;(j<=i && i*j<=2000000);j++) {
                if(i*j==red && ((i+2)*2+j*2)==brown) {
                    redwidth = i;
                    redheight = j;
                    break;
                }
            }
            if(redwidth!=0) break;
        }
        return new int[] {redwidth+2,redheight+2};
    }
}

빨간색이 1 이상 2,000,000 이하 이므로,

 

빨간색의 가로*세로가 1에서 2,000,000까지 i*i를 봤을 때, 딱 red와 떨어지면 정사각형 카펫임.

 

이 때는 red+2가 카펫의 가로, 세로임.

 

정사각형이 아니라면, 가로(redwidth, i)와 세로(redheight, j)를 보는데,

 

가로가 더 길 수 밖에 없으니, j는 i이하로, i는 조건대로 2,000,000이하로, i*j도 2,000,000이하로 잡고,

 

(i+2)*2 + j*2가 둘레인 갈색의 수가 되니,

 

이 조건이 맞으면 반복문에서 빠져나와 답으로 redwidth+2와 redheight+2를 반환.