[백준] 01타일(1904)

문제 설명

백준 01타일 문제 풀이(https://www.acmicpc.net/problem/1904)

코드 구현

const input =
  process.platform === "linux"
    ? require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
    : require("fs").readFileSync("./input.txt").toString().trim().split("\r\n");
 
const [N] = input[0].split(" ").map((el) => parseInt(el));
 
const dp = [0, 1, 2];
 
const tile = (n) =>
  dp[n] ? dp[n] : (dp[n] = (tile(n - 2) + tile(n - 1)) % 15746);
 
console.log(tile(N));

코드 해설

문제의 경우, N이 주어진다. 

• 1일 경우 0, 1
• 2일 경우 00, 11
• 3일 경우 100, 001, 111
• 4일 경우 1111, 0000, 0011,1100, 1001 

형태의 피보나치의 수를 이루게 된다. 즉 f(n-2) + f(n-1) = f(n) 형태의 점화식을 만족한다. 

해당 함수를 재귀를 이용하여 풀었으며, 재귀의 경우 반복 연산하는 것이 많아 배열을 통해 수를 저장하였다. 

메모리 제한이 256mb라 for문을 이용해서 푼 것이 아닌, memoization 하여 풀었다. 

요약 및 참고사항

• 문제는 앞에 경우가 뒤의 합이 된다. 해당 점화식 규직을 파악하면 쉽게 풀릴 수 있다.
• 조심해야 할 점은 수열의 개수를 15746 으로 나눈 결과여야 한다. 문제를 잘 읽자!