타일 장식물 - 프로그래머스
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
