타일링 방법의 수 세기 (난이도: 하)

2022. 10. 3. 22:24·알고리즘 (with JAVA)/동적 계획법

1. 문제 설명

(1) 2xN 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제가 있다고 하자.

 

(2) 타일들은 서로 겹쳐서는 안 되고 90도로 회전해서 쓸 수 있다.

 

(3) 예를 들어, N=5라고 하면, 아래의 그림과 같이 여덟 가지의 방법이 있다.

 

 

 

(4) 이때 N의 최댓 값이 100이라고 할 때 타일을 채우는 방법의 수를 찾는 프로그램을 작성하시오.

 

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 입력의 첫 줄에는 테스트 케이스의 수 C가 주어진다.

(2) 그 후 각 줄에 사각형의 너비(1<=N<=100)이 주어진다.

 

출력 조건

X

 

 

입력 예제

2

5

50

 

 

출력 예제

8
365010934

 

 

 

 

3. 제약 조건

X

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) 더 이상 사각형을 쪼갤 수 없는 경우

 

 

 

 

6. 코드

public class TILING2 {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int MOD=1000000007;

    private static int[] cache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            cache = new int[101];

            sb.append(solve(Integer.parseInt(sc.readLine()))+"\n");
        }
        System.out.println(sb);
    }
    private static int solve(int width) {
        // 기저 사례(1): 더 이상 사각형을 쪼갤 수 없는 경우
        if(width<=1) return 1;

        if(cache[width]!=0) return cache[width];

        // 가로 두 칸을 없앨 경우: solve(width-2)
        // 세로 두 칸을 없앨 경우: solve(width-1)
        return cache[width] = (solve(width-1) + solve(width-2)) % MOD;
    }
}

 

 

 

 

7. 점화식

저작자표시 (새창열림)

'알고리즘 (with JAVA) > 동적 계획법' 카테고리의 다른 글

우물을 기어오르는 달팽이 (난이도: 하)  (2) 2022.10.04
삼각형 위의 최대 경로 개수 세기 (난이도: 중)  (0) 2022.10.04
양자화 (난이도: 중)  (0) 2022.10.03
원주율 외우기 (난이도: 하)  (0) 2022.10.01
합친 LIS (난이도: 하)  (0) 2022.09.29
'알고리즘 (with JAVA)/동적 계획법' 카테고리의 다른 글
  • 우물을 기어오르는 달팽이 (난이도: 하)
  • 삼각형 위의 최대 경로 개수 세기 (난이도: 중)
  • 양자화 (난이도: 중)
  • 원주율 외우기 (난이도: 하)
백_곰
백_곰
  • 백_곰
    친절한 코딩
    백_곰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘 (with JAVA)
        • 기본 알고리즘
        • 완전 탐색
        • 분할 정복 알고리즘
        • 동적 계획법
        • 탐욕법
        • 코딩 테스트 기출 문제
        • 코드트리 조별과제
      • 백준 (with JAVA)
        • 완전 탐색
        • 분할 정복
        • 그 외
      • 자바
        • 개발 환경 구축하기
        • 팁
        • 기본적인 개념
        • 컬렉션 프레임워크
        • 프로세스와 쓰레드
        • 지네릭스
        • 람다식
        • 스트림
        • 입출력 IO
        • 네트워킹
        • 열거형(enums)
        • java.lang 패키지
        • java.time 패키지
        • 유용한 클래스들
        • 형식화 클래스들
      • 안드로이드 with 자바
        • 응용 문제들
        • 자잘한 문제들
        • 오류 보고서
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      InputStream
      불안정 정렬
      snail
      자바 개념
      선택 정렬
      Collections Framework
      코드트리
      중간연산
      ServerSocket
      스트림
      코딩테스트
      map()
      java.time 패키지
      소켓 프로그래밍
      코딩트리조별과제
      문자 기반 스트림
      outputstream
      다형성
      file
      역직렬화
      serializable
      안드로이드 스튜디오
      알고스팟
      TCP 소켓 프로그래밍
      java.lang패키지
      유용한 클래스
      제자리 정렬
      Arrays
      안정 정렬
      람다식
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    백_곰
    타일링 방법의 수 세기 (난이도: 하)
    상단으로

    티스토리툴바