[프로그래머스/JavaScript] 카펫

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

프로그래머스

---

1) 풀이

처음에는 어떻게 풀어야 할지 감이 안 오다가,

완전탐색 문제는 어차피 하나하나 확인하는 수밖에 없다고 생각하고 풀었더니 맞히게 되었다

 

우선 노란색 격자들이 안쪽에 배치되고, 이후에 그 둘레를 갈색 격자들이 감싸고 있는 형태이기 때문에

노란색 타일이 어떻게 배치되느냐에 따라 카펫의 가로, 세로 길이가 결정되므로 난 먼저 노란색 타일을 깔아본다고 생각했다. 하지만 여기서, 가로의 길이가 세로보다 길거나 같다고 했으므로 가로는 무조건 더 큰 숫자로 배치되어야 하기 때문에 yellow 변수의 제곱근을 올림한 수부터 나누어보았다.

(만약, yellow가 24라면  i에 5부터 들어가고, 5는 딱 떨어지게 나누어지지 않으므로 제일 처음 가로가 되는 숫자는 6, 세로가 되는 숫자는 4이다)

 

카펫의 가로 세로는 딱 떨어져야하므로 나머지가 0이 아니면 그다음으로 넘어가고 나누어떨어지면 yellow를 i로 나눈 값을 height에 넣어준다. 프로그래머스 예시만 봐도 알겠지만, brown의 개수는 i, 즉 노란색 격자의 가로 길이만큼과 그것의 우측 상단, 좌측 상단에 놓여지는 격자, 그리고 노란색 격자의 세로길이만큼의 2배(양쪽으로 감싸야하므로) 를 합한 것이 된다.

(이해가 안 된다면 해당 설명을 프로그래머스 예시 그림과 함께 보자!)

 

brown의 개수가 그것과 동일하다면, 정답을 return 해준다. 아니라면 또 다시 반복문이 돌면서 적절한 답을 찾을 것이다.

예전에 해당 문제를 백준에서 마주쳤을 때는 못풀었던 것 같은데, 지금은 조금만 고민하면 풀 수 있게 된 문제.. 오늘도 성장한 기분이다!

2) 최종 소스코드

function solution(brown, yellow) {
  let height = 0;
  for (let i = Math.ceil(Math.sqrt(yellow)); i <= yellow; i++) {
    if (yellow % i !== 0) continue;
    height = yellow / i;

    if (brown === (i + 2) * 2 + height * 2) return [i + 2, height + 2];
  }
}

3) 참고자료

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=diceworld&logNo=220198130087 

자바스크립트 거듭제곱 / 제곱근 (pow / sqrt)

https://brenden.tistory.com/10

[알고리즘] 완전탐색