타일 장식물 - 프로그래머스

benomadwill·2020년 6월 30일
0

Daily Algorithm

목록 보기
30/35

타일 장식물 - 프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43104

문제 설명

// 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

// 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
// [1, 1, 2, 3, 5, 8, .]
// 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

// 타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한 사항

// N은 1 이상 80 이하인 자연수이다.

입출력 예

// N : 5 => return 26
// N : 6 => return 42

분석

// 숫자 인풋 숫자 리턴
// 규칙을 찾는 것이 먼저다
// [1,1,2,3,5,8...]
// 1. 주어진 N에 맞춰 타일의 길이를 담은 숫자 배열을 리턴해야 한다
// 2. N : 5 인 경우 [1,1,2,3,5] 둘레는 가장 큰 (52) + ((3+5) 2)
// : 피보나찌 수

// 1. 주어진 N에 맞는 숫자 배열 만들기
// 2. 둘레 구하기(sort)

function solution(N) {
  // 1. 둘레가 담긴 박스 만들기
  let box = [1];
  // 1-1. 다음 둘레
  //   const fibo = (n) => (n < 2 ? n : fibo(n - 1) + fibo(n));
  // 1-2. 배열에 담기
  for (let i = 2; i <= N; i++) {
    box.push(fibo(i));
  }
  console.log(box);
  // ! Maximum callstack size exceeded
  // ! : 재귀함수를 사용할 경우 콜스택 사이즈 초과인듯..?
  // : 반복을 통한 피보나찌 함수
  function fibo(n) {
    var pre = 0;
    var cur = 1;
    var last = 0;
    for (var num = 1; num < n; num++) {
      last = pre + cur;
      pre = cur;
      cur = last;
    }
    return last;
  }
  // 피보나찌 2
  //   function fibo(n) {
  //     let arr = [0, 1];
  //     for (let i = 2; i <= n; i++) {
  //       arr.push(arr[i - 1] + arr[i - 2]);
  //     }
  //     return arr[n];
  //   }
  // 2. 둘레 구하기
  // 최대값 x2 + (그다음 최대값 + 최대값) x2
  let length = box.length;
  return box[length - 1] * 2 + (box[length - 1] + box[length - 2]) * 2;
}

후기

// 레벨3? 2?
// 난이도가 있는 문제 같은 경우는
// 수학적인 개념이 들어있는 경우가 많은 것 같다
// 그리고 그 수학적 개념을 파악한다면 문제 풀기가 수월해지는 것 같다
// 이번 문제는 동적 프로그래밍
// 나 같은 경우는 둘레가 피보나찌의 방식으로 늘어나는 것으로 파악해
// 다음 둘레를 피보나찌로 구해서 푸는 방식으로 했다
// 둘레의 경우도 간단한 규칙이 있는 것 같았다
// 다만 피보나찌로 둘레를 구할 때
// 재귀함수로 피보나찌 내부 함수를 만들었을 때 콜스택을 초과하는 것을 볼 수 있었다
// 테스트 통과 후 다른 사람들의 풀이를 보니...
// 피보나찌 내부함수를 사용하지 않더라도 다양하게 푸는 방법이 존재했다
// 역시...답은 하나가 아니다

solution

function solution(N) {
  let fibo = [4, 6];
  for (let i = 2; i < N; i++) {
    fibo[i] = fibo[i - 1] + fibo[i - 2];
  }

  return fibo[N - 1];
}

동적계획법 : https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

profile
BenomadWill

0개의 댓글