알고리즘

[백준] 11727번, 2xn 타일링2

2023. 6. 21. 02:34
728x90
반응형

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

문) 2×n 크기의 직사각형을 1×2, 2×1, 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입) 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출) 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.


풀이

1. 테이블 정의
 - 2xn크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지 값
1) 입력받은 n의 크기에 해당하는 직사각형을 채울 경우의 수 → 피보나치 수열
2) 경우의 수를 10,007로 나눈 값을 구하고 출력


2. 점화식 : D[n] = D[n-1] + D[n-2]*2
3. 초기값 정하기 : D[0] = D[1] = 1

✅ 점화식 도출 과정

▶n = 2
2 = 1+1, (2)*2
▶n = 3
3 = 1+1+1, (2+1, 1+2)*2
▶n = 4
4 = 1+1+1+1, (1+1+2, 1+2+1, 2+1+1, 2+2) *2

 

Scanner만 활용하였고, 메모리 17756KB - 시간 212ms 소요.
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] D = new int[n+1];
        D[0] = D[1] = 1;

        if (n < 2) {
            System.out.print(1);
        } else {
            for(int i=2; i<n+1; i++) {
                D[i] = (D[i-1] + D[i-2]*2) %10007;
            }
            System.out.print(D[n]);
        }
        sc.close();
    }
}

 

[참고]

2023.06.21 - [알고리즘] - [백준] DP - 11726번, 2xn 타일링(점화식 도움)

저작자표시 비영리 (새창열림)

'알고리즘' 카테고리의 다른 글

[백준] DP - 10844번, 쉬운 계단 수 (답지 봄)  (0) 2023.09.22
[백준] DP - 9095번, 1, 2, 3 더하기  (0) 2023.06.22
[백준] DP - 11726번, 2xn 타일링(점화식 도움)  (0) 2023.06.21
[백준] DP - 1463번, 1로 만들기  (0) 2023.06.16
[백준] 입출력 - 10992번, 별찍기 17  (0) 2023.03.23
'알고리즘' 카테고리의 다른 글
  • [백준] DP - 10844번, 쉬운 계단 수 (답지 봄)
  • [백준] DP - 9095번, 1, 2, 3 더하기
  • [백준] DP - 11726번, 2xn 타일링(점화식 도움)
  • [백준] DP - 1463번, 1로 만들기
hatch
hatch
250x250
hatch
차근차근 쌓아올리는,
hatch
전체
오늘
어제
  • 분류 전체보기 (121)
    • TIL (3)
    • [JAVA] (17)
      • 생활코딩 (11)
    • 모바일 (25)
      • android (24)
      • ReactNative (1)
    • 웹개발 (25)
      • React (3)
      • jQuery (5)
      • Springboot (2)
    • 알고리즘 (42)
    • [프로그래밍기초지식] (1)
    • [기술문서 읽기] (0)
      • 개념 번역 (0)
    • 인사이트(insight) (2)
    • git (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • write
  • manger

공지사항

인기 글

태그

  • 재귀
  • 별찍기
  • 반복문
  • 모프2주차
  • javascript
  • 백준
  • 타일링
  • BufferedReader
  • scanf
  • Doit!자바프로그래밍입문
  • state
  • 210908
  • 명시적 인텐트
  • jquery
  • 중복리니어레이아웃
  • 깊은복사
  • 노이클립스
  • TIL
  • DP
  • 안드로이드프로그래밍6판

최근 댓글

최근 글

hELLO · Designed By 정상우.
hatch
[백준] 11727번, 2xn 타일링2
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.