카펫

YEONGHUN KO·2021년 12월 19일

완전탐색

ALGORITHMS - PRACTICE

목록 보기

42/50

1. 카펫

갈색과 노란색으로 이루어진 카펫이 있다. 아래 그림처럼.

carpet

노란색 타일이 중간에 있고 그 겉을 갈색 타일이 감싸고 있다. 노란색 타일의 총 갯수는 2개이고 갈색타일은 8개이다. 이때 카펫의 가로는 4이고 세로는 3이다. 노란색 타일과 갈색타일의 총갯수가 주어졌을 때 카펫의 가로 세로를 리턴하면 된다.(가로의 길이 >= 세로의 길이)

입출력 예
brown	yellow	return
10	      2	    [4, 3]
8	      1	    [3, 3]
24	      24	[8, 6]

2. 접근 방법

두가지 경우가 있다. 하나는 노란색카펫을 이루는 숫자의 약수의 갯수(즉 가로와 세로의 조합)를 구하는 법이고 나머지 하나는, 전체 가로의 길이를 3에서 부터 1씩 늘려가면서 구하는 방법이 있다.

우선 노란색카펫의 가로를 m, 세로를 n이라고 했을때 전체 갈색 카펫의 총 갯수는 (m+2)*(n+2)-(m*n) 이다. 그리고 전체 카펫의 가로세로의 길이는 m+2,n+2이다.

그럼 약수의 갯수를 통해 구하는 방법부터 알아보자

2-1. solution1

function findDivisor(int) {
  let arr = [];
  let comb = [];

  for (let i = 0; i < int + 1; i++) {
    if (int % i === 0) {
      arr.push(i);
    }
  }

  for (let j = 0, k = arr.length-1; j <= k; j++, k--) {
    comb.push([arr[k], arr[j]]);
  }

  return comb;
}

function solution1(brown, yellow) {
  let answer = [];

  let yellowComb = findDivisor(yellow);

  for (let i = 0; i < yellowComb.length; i++) {
    if ((yellowComb[i][0] + 2) * (yellowComb[i][1] + 2) === yellow + brown) {
      return [yellowComb[i][0] + 2, yellowComb[i][1] + 2];
    }
  }
}
음... 왜 모두 통과하지 못했을까??
개선해보자. 생각해보자
yellow만 가지고 계산해냄
brown을 사용하지 않았음
예를 들어서 yellow의 타일의 갯수가 12개라고 할때, yellow의 가로세로길이가 [4,3]일 수 도 있지만 [6,2]일 수 도 있잖아.

그렇지!!!!!!
풀었다 풀었어....
머릿속이 굉장히 복잡한 가운데 멘탈 잡고 풀었다... 하 이렇게 감격스러울 수가. 지금 나는 지금 상태로 충분히 만족하다 정말....
주님 감사합니다!!

근데 이 로직은 맨처음엔 위의 것과 조금 달랐다. brown의 길이를 사용하지 않고 바로 yellowComb의 제일 마지막 comb를 return했다. 하지만 꼭 마지막 조합일 필요는 없다. 예를 들어서 yellow의 총 타일갯수가 12개 일때,[4,3]이 될 수 도 있지만 [6,2]가 될수도 있기 때문. 따라서 brown의 갯수를 이용 할 수 밖에 없다.

2-2. solution2

카펫 전체 가로길이를 3에서 시작해서 하나씩 늘려가는 로직이다.

function solution2(brown, yellow) {
  let answer = [];
  // i가 3에서 시작하는 이유는 최소세로의 길이가 3이므로

  for (var i = 3; i <= (brown + yellow) / i; i++) {
    // 전체를 세로길이로 나누면 가로갈이가 나옴
    var x = Math.floor((brown + yellow) / i);
    // x는 전체의 가로, i는 전체의 세로를 의미
    if ((x - 2) * (i - 2) === yellow) {
      break;
    }
  }
  return [x, i];
}