[백준] 11726번 2 x n 타일링 자바 풀이

2024. 2. 21. 10:14·알고리즘

문제

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초 256 MB 166553 64421 47778 36.624%

문제

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

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

입력

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

출력

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

풀이

아래처럼 실제로 직사각형을 채우는 방법을 나열 해본 후 n번째 직사각형을 채우는 방법은 n-1번째와 n-2번째의 합이라는 것을 알 수 있었다.

이 후 방법의 수를 10,007로 나누어 출력해줬다.

1 - 1
1

2 - 2
1 1
2 2

3 - 3
1 1 1
1 2 2
2 2 1

4 - 5
1 1 1 1
1 2 2 1
2 2 1 1
1 1 2 2
2 2 2 2

5 - 8  
1 1 1 1 1
1 2 2 1 1
2 2 1 1 1
1 1 2 2 1
2 2 2 2 1
1 1 1 2 2
1 2 2 2 2
2 2 1 2 2

 

코드

package com.company.baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B11726 {
	static long[] dp = new long[1001];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());

		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 3;
		for (int i = 4; i <= n; i++) {
			dp[i] = (dp[i-1] % 10007) + (dp[i-2] % 10007);
		}

		System.out.println(dp[n] % 10007);
	}
}

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

[백준] 파이프 옮기기 1 자바 풀이  (0) 2024.02.29
[백준] 14503번 로봇 청소기 자바 풀이  (1) 2024.02.25
[백준] 1976번 여행 계획 자바 풀이  (0) 2024.02.20
[백준] 1744번 수 묶기 자바 풀이  (3) 2024.02.20
[프로그래머스] 등굣길 자바 풀이  (2) 2023.12.28
'알고리즘' 카테고리의 다른 글
  • [백준] 파이프 옮기기 1 자바 풀이
  • [백준] 14503번 로봇 청소기 자바 풀이
  • [백준] 1976번 여행 계획 자바 풀이
  • [백준] 1744번 수 묶기 자바 풀이
HWBB
HWBB
흥미주도개발자
  • HWBB
    코딩공부방
    HWBB
  • 전체
    오늘
    어제
    • 분류 전체보기 (161)
      • 알고리즘 (61)
      • Android (27)
      • Kotlin (0)
      • Java (2)
      • Design Pattern (2)
      • React Native (1)
      • Python (0)
      • TIL (20)
      • Unity (0)
      • React (2)
      • AWS (0)
      • Git (11)
      • MFC (1)
      • Spring (4)
      • Computer Science (4)
      • Vue (4)
      • Infra (4)
      • 박현우 (10)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 승윤이
  • 공지사항

  • 인기 글

  • 태그

    coding
    알고리즘
    algorithm
    안드로이드 스튜디오
    Java
    코딩테스트
    baekjoon
    프로그래머스
    Android
    Kotlin
    깃허브
    programmers
    안드로이드
    C++
    github
    android studio
    GIT
    백준
    코틀린
    자바
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
HWBB
[백준] 11726번 2 x n 타일링 자바 풀이
상단으로

티스토리툴바