[백준/BOJ] 11727번 : 2Xn 타일링 2 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

- 문제 -

 

난이도 실버 3 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

https://comain.tistory.com/303

[백준/BOJ] 11726번 : 2Xn 타일링 (JAVA / 자바)

이름처럼이나 매우 비슷한 문제이다. 같은 점화식이지만 패턴이 좀 다르다.

일단 쉽게 가짓수를 구할 수 있는데까지 구해보자.

n이 1일때 1.

n이 2일때 3. ll, = , ㅁ

n이 3일때 5. lll, l=, =l, ㅁl, lㅁ

n이 4일때 11. llll, ll=, l=l, =ll, ==, ㅁll, lㅁl, llㅁ, ㅁ=, =ㅁ, ㅁㅁ

n이 5일때 21이다. 5는 가짓수가 급격히 많아지니 가짓수만 적겠다.

여기까지만 봤을때 얼추 보인다. 3에서 5가 되려면 2가 필요하고, 5에서 11이 되려면 6이 필요하다. 11에서 21이 되려면 10이 필요하다.

n = 2 > n = 3 차이는 2.

n = 3 > n = 4 차이는 6.

n = 4 > n = 5 차이는 10.

보면 알겠지만 차이가 전전 값의 2배와 같다.

이 말은 n = 3이면, n이 2일때 값인 3과 n이 1일때 값인 1 * 2의 합과 같은 것이다.

아무래도 경우의 수가 5까지라 적으니 해당 점화식으로 8까지 구해보자.

n = 5 : 11 + 5 * 2 = 21

n = 6 : 21 + 11 * 2 = 43

n = 7 : 43 + 21 * 2 = 85

n = 8 : 85 + 43 * 2 = 171

예제랑 같다 이정도면 해당 식이 증명 된것 같으니 코드를 보자.

---

-풀이-

 

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

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];
		
		dp[0] = 1;
		dp[1] = 1;
		for(int i = 2; i <= n; i++) {
			dp[i] = (dp[i - 1] + (dp[i - 2] * 2)) % 10007;
		}
		System.out.println(dp[n]);
	}

}

---

-결과-

 

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.