프로그래머스 2xn타일링을 풀어보자

JD·2021년 11월 18일
0

중요사항

  • 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return

📢2xn타일링

2 n 의 직사각형 안에 1 2 직사각형이 들어갈수있는 경우의수를 모두 구하라

📢풀이

n경우의수n경우의수
1145
2258
33613
  • n값이 1~6일때의 경우의수를 계산하여 이 사이에 연관에 대해생각
  • 무슨 관계인지 찾다 현재항의 결과값은 전항과 전전항의 값인걸 발견함
  • 경우의수 가 바뀌는 부분은 4부터이므로 전전항값을 2 전항을 3으로 변수선언
  • for문을 사용하여 n까지 반복
  • 경우의 수가 많아 질 수 있으므로 1,000,000,007을 반복문 안에 결과값과 나누고 반환

코드사진

class Solution {
    public int solution(int n) {
        int answer = 0;
        int preint=2;
        int nextint=3;
            
            for(int i=3; i<n; i++ ){
                answer = (preint+nextint)%1000000007;
                preint=nextint;
                nextint=answer;
            }
           
        
        return answer;
    }
}

📢마치며

수열이름을 모르고 풀었는데 이런 수열을 피보나치 수열이라고 하고 전항과전전항을 더하여 현재항을 구하는 방식으로 알고리즘 문제에서 많이 나온다고 하니 기억하고있어야겠다 다풀고 나서 다른 방식은 뭐가 있나 생각해보니까 재귀함수로 작성하여 풀수있을꺼같은데 다음번에 이런문제가 나온다면 재귀함수로 작성해봐야겠다

📢출처

👍프로그래머스

0개의 댓글