[C#] 카펫 색깔 숫자 세기

카펫 색깔 숫자 세기

문제 설명

Leo는 카펫을 사러 갔다가
중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때
카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.
(카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.)

풀이

접근 방법

1번 힌트 : 가로와 세로 길이의 합과 brown의 관계

가로 세로 크기의 합 * 2 - 4 = brown

• brown은 카펫의 테두리를 1줄 감싸고 있으므로 가로와 세로의 길이의 합에서 겹치는 부분 4군데를 빼면 brown에 해당하는 면적을 구할 수 있다.
  □□□□ □ : 갈색
  □■■□ ■ : 노란색
  □□□□
• 이러한 구조의 카펫이라고 할 때 가로와 세로는 각각 4와 3이다.
  • (4 + 3) * 2 - 4 = 10 = brown

2번 힌트 : 전체 면적과 가로 세로의 관계

가로 * 세로 = sumOfArea

• 이는 당연한 힌트이다. 가로 길이와 세로 길이의 곱이 넓이로 정의되어 있기 때문이다.
  따라서 brown + yellow는 가로와 세로의 곱이 된다.

• 이 두 가지 힌트를 통해 가로와 세로 길이에 대한 2개의 식을 구할 수 있고, 이를 하나의 변수에 대해 식을 정리하여 가로 또는 세로의 길이를 구할 수 있다.

2차식 정리하기

width = 'sumOfArea' / height 이므로
(width + height) * 2 - 4 = brown 식을 height에 대해 정리할 수 있다.
2 * height + 2 * (sumOfArea / height) - 4 = brown
height는 양수 이므로 양 변에 곱해준다.
→ 2 * height ^ 2 + 2 * sumOfArea - 4 * height = brown * height
→ 2 * height ^ 2 - (brown + 4) * height + 2 * sumOfArea = 0

최종적으로 산출된 식은 다음과 같다.
f(height) = A * height ^ 2 + B * height + C
A = 2
B = - (brown + 4)
C = 2 * sumOfArea

height 구하기

private int CalculateHeight(int sumOfArea, int brown)
{
	// f(height) = A * height ^ 2 + B * height + C
    // A = 2
    // B = - (brwon + 4)
    // C = 2 * sumOfArea
        
    double discriminant = Math.Pow(4 + brown, 2) - (16 * sumOfArea);
        
    // 판별식이 음수이면 실근이 없으므로 유효한 해가 없습니다.
    if (discriminant < 0)
    	return -1; // 또는 예외 처리
        
	double sqrtDiscriminant = Math.Sqrt(discriminant);
        
    double height1 = ((4 + brown) + sqrtDiscriminant) / 4.0;
        
    double height2 = ((4 + brown) - sqrtDiscriminant) / 4.0;
        
    if(height1 > height2)
    	return (int)height2;
	else
    	return (int)height1;
}

• height에 대해 정리한 2차식을 먼저 판별식을 사용해 해가 있는지 여부를 판단한다.
• 해가 있다고 판명된 경우(문제 조건에서는 대부분 해가 있다고 판명될 것이다.)
  근의 공식을 활용해 2개의 해를 구한다.
• 문제 조건에서 가로가 세로의 길이보다 길다고 했으므로 두 개의 해 중에서 더 작은 값을 height로 반환한다.

width 구하기

private int CalculateWidth(int sumOfArea, int height)
{
	return sumOfArea / height;
}

• 앞서 힌트에서 보았던 대로 전체 면적을 이용해 width를 구해준다.

최종 정답 도출

public int[] Solution(int brown, int yellow) {
//가로 크기, 세로 크기 순서
int[] answer = new int[2];

int width = 0;
int height = 0;
        
int sumOfArea = brown + yellow;
        
height = CalculateHeight(sumOfArea, brown);
        
if(height == -1)
	throw new Exception("Can not find correct height");
        
width = CalculateWidth(sumOfArea, height);
        
answer = [width, height];
        
return answer;
}

• 올바른 해를 찾지 못했을 경우의 예외 처리를 해준다.
• 앞서 만든 함수를 이용해 가로와 세로의 길이를 구해 반환한다.