[알고리즘] 백준 1904 01타일

📖문제

01타일

 

 

❓구상

패턴의 개수를 파악하는 문제는 작은 규모의 패턴을 파악해서 해결하기 좋은 동적 프로그래밍(Dynamic Programming)

계획법으로 풀기 적합한 문제이다.

일반적인 이진법이라면 N이 1일때 0과 1을 만들 수 있기 때문에 2가 나와야하지만, 이 문제의 조건을 살펴보면 아래와 같다.

1. 이진법을 구성할 때 1과 00의 조합으로만 구성을 해야한다.
2. 0은 01 혹은 10 처럼 사용할 수 없고 0이 2개가 붙어있어야한다.

주어진 N에 따라 표현될 수 있는 이진법의 종류를 알아보면 패턴을 파악할 수 있을것으로 기대된다.

 

🎲 패턴

N이 1일때 부터 7일때 까지의 패턴을 파악한 결과 피보나치 수열처럼 dp[i] = dp[i-1] + dp[i-2] 의 패턴을 가지고 있음을 알 수 있다.

이 것을 바탕으로 코드를 작성해보자.

 

코드.

const N = require("fs").readFileSync("./input.txt", "utf-8").trim();
const dp = [1, 2];
const NUMBER_OF_DIVIDE = 15746;
const solution = (n) => {
  for (let i = 2; i < n; i++)
    dp[i] = (dp[i - 1] + dp[i - 2]) % NUMBER_OF_DIVIDE;
};
solution(N);
console.log(dp[N - 1]);

 

 

 

🔥배운 점

이전에 올린 백준 1003 피보나치 함수 글에서 "큰 문제를 작은 단위의 문제로 분해 하여 패턴을 파악해야하는 점" 을 잊지 않고 DP 문제를 풀때 염두해 두었더니어느정도 동적 계획법에 익숙해졌다고 생각했고, 유사한 형태의 DP 문제는 어느정도 풀 수 있게 된것 같다. 하지만, 다른 패턴으로 DP 계획법을 사용하는 경우는 여전히 문제를 해결하는데 어려움이 있다. 단순히 피보나치 수열의 프레임을 갖는 DP 이외에 해결법에 대한 학습이 추가로 필요한 것 같다.