[프로그래머스] Lv2 - 카펫

문제

프로그래머스 코딩테스트 고득점 Kit - 완전 탐색

• Lv 2. 카펫 (Java)

문제 설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

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

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

제한사항

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

입출력 예

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

풀이

접근 방식

• 주어지는 갈색 격자의 갯수와 노란색 격자의 갯수를 통해 최종적으로 이루어지는 카펫의 가로와 세로 길이를 구해야 한다.
• 이에 존재하는 공식들
  • 카펫의 총 격자 수 = 갈색 격자 수 + 노란색 격자 수
  • 갈색 격자가 외각을 이루고 노란색 격자가 내부를 이루기 때문에 대각선에 있는 격자에 의해 아래와 같은 규칙이 존재

    갈색 격자의 가로 = 노란색 격자의 가로 + 2
    갈색 격자의 세로 = 노란색 격자의 세로 + 2

  • 이는 반대로 따졌을 때, 노란색 격자의 가로와 세로 길이를 구할 수 있게 된다.

    노란색 격자의 가로 = 갈색 격자의 가로 - 2
    노란색 격자의 세로 = 갈색 격자의 세로 - 2

  • 카펫의 가로 ≥ 카펫의 세로 는 즉, 갈색 격자의 가로 ≥ 갈색 격자의 세로 와 같다.

코드 구현

정답 코드

public int[] solution(int brown, int yellow) {

    int[] answer = new int[2];

    int y_garo, y_sero;     // 노란색 격자의 가로, 세로 ( 카펫 내부 )
    int b_garo, b_sero;     // 갈색 격자의 가로, 세로 ( 즉, 카펫의 외각선인 가로와 세로 길이 ) -> 최종적으로 구해야함
    int sum;

    sum = brown + yellow;   // 카펫 격자 수의 합계

    // 최종 격자 수에 대한 여러 가로와 세로의 경우의 수를 따져가며 조건에 맞는 정답 찾기
    for (int i = 1; i <= sum; i++) {
        if (sum % i == 0) { // 총 카펫의 격자 수를 나눌 때, 나누어 떨어지는 수들의 경우만 따지기

            b_sero = i;         // 갈색 격자의 세로
            b_garo = sum / i;   // 갈색 격자의 가로

            if (b_garo < b_sero) {  // 가로가 세로보다 작으면 빠져나가기 ( 가로 >= 세로 )
                break;
            }

            y_garo = b_garo - 2;    // 내부에 있는 노란 격자의 가로
            y_sero = b_sero - 2;    // 내부에 있는 노란 격자의 세로

            if (y_garo * y_sero == yellow) {
                answer[0] = b_garo;
                answer[1] = b_sero;
            }
        }
    }

    return answer;
	}
}

실행 결과