🔗 링크

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

2️⃣ 문제

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있다.

이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 하는데,

가능한 경우의 수를 구하고, 수의 1000000007를 나눈 나머지를 구해야한다.

👀 예제로 문제 파악하기

n 1 : 1가지
n 2 : 2가지
n 3 : 3가지
n 4 : 5가지
n 5 : 8가지 ...

→ 피보나치 수열

😮 알고리즘 풀이 순서

1. 변수 두 개(a, b)의 초기값을 각각 1로 지정해둔다.
2. 1부터 n만큼 반복문을 돈다.
   1. answer에 변수 두개를 더하고 1000000007를 나눈 나머지를 대입한다.
   2. a에는 b값을, b에는 answer값을 대입한다.
3. answer를 리턴한다.
   
   

👩‍💻 코드

public class Solution {
  public int solution(int n) {
    int answer = 1;

    int a = 1;
    int b = 1;

    for (int i = 1; i < n; i++) {
      answer = (a + b)  % 1000000007; // 마지막에 나눠주면 overflow가 나기 때문에 계산 과정에서 나눔
      
      a = b;
      b = answer;
    }
    
    return answer;
  }


  @Test
  public void 정답() {
    Assert.assertEquals(5, solution(4));
    Assert.assertEquals(8, solution(5));
    Assert.assertEquals(1, solution(1));
  }
}