[이취코] CH 08. 실전 문제 바닥 공사_ 다시 풀어보기

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

본 게시글은 해당 책에 나와있는 문제를 풀고 기록한 것으로 해당 코드의 문제를 확인하고 싶다면 위의 링크를 통해 책을 구입한 후

책 ch08 223p를 참고하기를 바란다.

 

문제

CH 08. 실전 문제 바닥 공사

해당 문제는 2*N길이의 타일이 있을때 2*1,1*2,2*2 타일들로 2*N을 덮을 수 있는 경우의 수를 구하는 프로그램을 작성하는 문제이다.

 

  문제접근 방법   

처음에는 경우의 수를 구하고 규칙을 찾는 식으로 문제를 접근하려하였으나 문제에서 제공하는 예제의 수가 하나로 비교값을 구하는데는 어려움이 있을 것으로 인지 후 문제를 접근했다. 해당문제에서 경우의 수는 총 3가지였다. n의 길이를 가지는 타일에 마지막에 1*2가 오는경우 2*1 혹은 2*2가 오는 경우 이렇게 3가지이다. 첫경우 1*2만큼을 제외시키면  (n-1)*2만큼이 남고 두번째, 세번째의 경우 둘다 (n-2)만큼이 남았다. 이를 식으로 작성해보니 배열[n]=배열[n-1]+배열[n-2]*2라는 점화식을 도출할 수 있었다.

이값이 맞는지 확인해보기위해서 3을 넣어보니 값이 잘나왔고 혹시몰라 직접 n=4일때를 그려보고 비교했을때도 답이 같아 아래와 같은 코드를 작성하였다.

 

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        
        int dp[]=new int[n];
        dp[0]=1;
        if(n>1)dp[1]=3;
        for(int i=2;i<n;i++){
            dp[i]=(dp[i-1]+dp[i-2]*2)%796796;

        }
        System.out.print(dp[n-1]);
    }
}

 

  마무리  

현재 본 책의 예제를 순서대로 풀어보고 있었는데 문제를 풀어보고 풀이를 보면서 어떤식으로 접근해야하는지에 대한 감이 오는 것같아서 좋았다.