[프로그래머스] Level 2. 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

프로그래머스

 

[풀이과정]

중앙이 노란색이고 테두리 1줄이 갈색이면

1. 노란색 타일로 만들 수 있는 모든 사각형의 경우에서 1줄의 갈색 테두리에 필요한 갈색 타일 개수를 비교한다.

2. 갈색 타일로 만들 수 있는 모든 경우의 테두리 속을 채울 노란 타일의 개수를 비교한다.

 

갈색 타일의 개수는 8이상 5,000이하이고 노란 타일의 개수는 1 이상 2,000,000이하이기 때문에

갈색 타일을 기준으로 경우를 따지는 것이 시간복잡도가 더 작을 것이라고 판단.

 

갈색 타일 개수를 2로 나누면 (ㄴ, ㄱ) 의 모양 두 개로 나눌 수 있는데, 이 때 한 변의 길이에서 -1 한 값은 노란 사각형의 한 변의 길이 이다.

ex) 10 / 2 = 5 개의 타일로 이루어진 ㄱ 모양에서 모서리 부분(빨간 박스)를 뺀 타일의 개수로 만들 수 있는 사각형의 경우를 구한다.

 

[내 코드]

class Solution {
    public int[] solution(int brown, int yellow) {
        int sumOfHoriVerti = brown / 2 - 2;
        int[] answer = new int[2];
        for(int verti = 1; verti <= sumOfHoriVerti - verti; verti++){
            int hori = sumOfHoriVerti - verti;
            if(yellow == verti * hori){
                answer[0] = hori + 2;
                answer[1] = verti + 2;
            }
        }
        return answer;
    }
}

 

[다른 사람 코드]

import java.util.*;
class Solution {
    public int[] solution(int brown, int yellow) {
        int a = (brown+4)/2;
        int b = yellow+2*a-4;
        int[] answer = {(int)(a+Math.sqrt(a*a-4*b))/2,(int)(a-Math.sqrt(a*a-4*b))/2};
        return answer;
    }
}

-> a는 카펫의 가로, 세로 길이의 합이고 b는 노란 타일과 브라운 타일의 합임. int b = yellow + brown 으로 하면 됨.

a = x + y, b = xy 로 둔 후 계산

수학적으로 접근했을 때의 장점이 있을까? 입력값이 매우 커지면 장점이겠지만..