[완전탐색]카펫

문제

문제 설명

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

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

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

제한사항

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

입출력 예

brownyellowreturn

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

문제풀이

1. 노란색과 갈색의 총 갯수의 모든 약수를 구한다.
2. 주어진 약수의 쌍인 width와 height값을 이용하여 카펫 중앙에 배치될 수 있는지 비교한다.

코드

function solution(brown, yellow) {
  var answer = [];
  let size = brown + yellow; //카펫의 총 갯수

  for (let i = 1; i <= size; i++) {
    let width = i;
    let height;
    if (size % width !== 0) continue; // 약수가 아닌 경우에는 그 다음 순회
    else height = size / width;
    if (width < height) continue; // 가로는 세로보다 항상 김
    let center = Math.floor(width / 2); // 현재 카펫의 중앙에 위치될 수 있는 값
    let remain = yellow - center; // 중앙에 위치될 수 있는 값에 노란 카펫이 적재될 수 있는지 식별
    if (remain < 0) continue; //노란 카펫을 깔 공간이 없는 경우
    if (remain > 0) { //노란 카펫이 남아 있는 경우
      let total = center * height;
      if(total === yellow) { 
        answer.push(width);
        answer.push(height);
        return answer;
      } else continue;
    }
    if (remain === 0) { //딱 맞는 경우
      answer.push(width);
      answer.push(height);
      return answer;
    }
  }
}

 

오답

주어진 예시 케이스는 모두 다 맞았지만 테스트 케이스를 돌렸을 때는 몇 개의 경우가 오답으로 처리되었다.

 

이에 문제를 좀 더 간단하게 생각해보기로 했다.

 

사실 이 문제에서는 갈색의 갯수가 몇 개인지는 크게 중요하지 않다.

갈색의 카펫은 상시 노란색의 카펫을 둘러 싸고 있기 때문에 노란색 카펫 기준으로 둘러 싸인 경우의 수를 계산해 주는 식으로 접근한다면 쉽게 풀 수 있는 문제였다.

 

현재 예시에서 주어진 카펫에 노란 카펫의 가로 너비는 2이고 세로 너비는 1이다.

이 말은 즉슨, 노란 카펫을 둘러 싸고 있는 갈색 카펫 갯수는 (노란 카펫 가로 너비 × 2) + (노란 카펫 세로 너비 × 2)를 통해 간접적으로 구할 수 있고 이 식에 나머지 구석에 위치한 갈색 카펫 갯수인 4를 계산한 결과 값을 주어진 갈색 카펫의 갯수와 비교한다면 문제의 답을 구할 수 있다.

 

코드

function solution(brown, yellow) {
    for(let i=1; i<=Math.ceil(yellow/2); i++) { // index가 뜻하는 것은 노란색 카펫의 높이(높이는 가로보다 커질 수 없기 때문에 가로 너비가 같아지는 경우까지만 순회)
        let tmp = yellow % i; 
        if(tmp === 0) { // 노란 카펫에 남김 없이 들어맞는지 식별
            const width = yellow/i;
            if((width+i)*2+4 === brown) return [width+2, i+2] // 모서리의 나머지 값까지 합산해줘야 총 너비 및 높이를 반환할 수 있음
        }
    }
}

 

고찰

사실 해당 문제에 대해서 포스팅을 할지 고민을 하였다.

 

어떤 특정한 알고리즘 개념에 대한 지식이 선제되어 있어야 풀 수 있는 것이 아니라 주어진 도식에 대해서 분석하고 이를 식으로 표현할 수 있는가에 대한 문제 해결 능력에 대해서 시험하고 있는 문제였기 때문이다.

 

하지만 일전에 카카오 문제 중 거리두기 확인하기 또한 이와 비슷하게 도식화된 문제였고 헤밀턴 거리에 대해서 제대로 된 이해와 이를 활용할 수 있는 해결 능력을 요구하는 문제였지만 제대로 풀이하지 못하였다.

 

문제의 전체적인 스타일이나 난이도는 다르지만 해당 문제를 풀이했던 바와 같이, 앞으론 도식화 문제에 대해서 주어진 상황을 명확히 파악하고 규칙을 발견 및 식으로 간단화할 수 있는 능력을 최대한 배양할 수 있도록 좀 더 노력해야 할 것 같기에 해당 문제에 대해서 포스팅 해보았다.