[Algorithm] 카펫 - JavaScript

프로그래머스 - 카펫
난이도 : Level 1

▶ 풀이

길이를 기준으로 반복문을 돌리며 w * h 의 값이 brown + yellow 의 값인 수를 찾고 그 수 중 테두리를 제외한 높이와 넓이가 노란 타일의 수와 같을 경우 출력한다.

function solution(brown, yellow) {
  // 길이의 최소값이 3이기 때문에 h 는 3부터 시작한다.
    for(let h = 3; h <= brown; h++) {
      //갈색 타일과 노란 타일을 더한 값이 길이와 맞아 떨어질 때
        if((brown + yellow) % h === 0) {
          // 넓이는 타일의 합을 길이로 나눈 값이다. 
          //(brown + yellow 의 값은 h * w 와 항상 일치하다)
            let w = (brown + yellow) / h;            
            //태두리를 빼고 곱한 값이 노란 타일의 수일 경우.
            if( (h - 2) * (w - 2) === yellow) {
              // 출력한다.
                return [w, h];
            }
        }
    }
}

▶ 다른 풀이

function solution(brown, yellow) {
    const x = (brown - 12) * 0.5;
    const y = yellow - brown + 8;
    const i = ( 8 + x + Math.sqrt( Math.pow(x, 2) - (4 * y) ) ) * 0.5;
    const j = ( 8 + x - Math.sqrt( Math.pow(x, 2) - (4 * y) ) ) * 0.5;
    console.log(i)


    var answer = [i, j];
    return answer;
}

근의 공식을 사용한 풀이이다.

아래 식처럼 식을 단순화할 수 있다.

w + h = (brown + 4) / 2
w * h = brown + yellow

(brown + 4) / 2 를 A 로 두고
brown + yellow 를 B로 둔 후 위 식을 바꿔보면

pow(h, 2) - (A * h) + B = 0

이 된다. 이 녀석의 형태가 이차방정식이니, 이 녀석을 근의 공식으로 푼 후,
가로가 세로보다 크거나 같으므로 가로인 w는 b(제곱) - 4ac 를 더하고 세로인 h는 빼면 값을 구할 수 있다.

▶ 마치며

고등학교 때인가 중학교일 때 배운 근의 공식, 아예 써먹을 수 없는 건 아니었다. 그때 뇌가 알고리즘은 더 잘 풀 수 있겠는데?