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

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

 

 

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

11726번: 2×n 타일링

---

- 문제 -

 

난이도 실버 3 문제이다.

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

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

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

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

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

dp문제에서 상당히 쉬운편에 드는 점화식 문제이다.

근거는 노트에 직접 도형을 그려가면서 확인해본 결과 점화식이였다.

n이 1일때 1가지의 방법이 있다.

n이 2일때 2가지의 방법이 있다.

n이 3일때 3가지의 방법이 있다.

n이 4일때 5가지의 방법이 있다. 여기까지는 딱히 그리지 않아도 쉽게 구할 수 있을 것이다.

예제2번에 n이 9일때 55라고 한다. 점화식으로 9까지 가보자.

1 > 1

2 > 2

3 > 3

4 > 5

5 > 3 + 5 = 8

6 > 8 + 5 = 13

7 > 13 + 8 = 21

8 > 21 + 13 = 34

9 > 34 + 21 = 55

예제랑 같다. 점화식이란 것을 알았으니 점화식으로 풀어보겠다.

 

점화식은 쉽지만 정답확률은 35프로밖에 안된다. 이유는 크게 두가지로 예상이 된다.(사실 필자가 그렇게 틀렸다.)

1. 마지막에 10007로만 나눈 경우. 연산과정에서 long의 범위를 넘어서기 때문에 오버플로우가 난다.

2. 100%에서 ArraysIndex Error가 나오는 경우. 입력은 1부터 1000까지 주어진다. 보통 인덱스 1에는 1을 넣고, 인덱스 2에는 2를 저장한 뒤, 반복문을 통해 다음 인덱스 값을 구할 것이다. 하지만 그럴 경우 1이 입력되었을때 해당 에러가 뜬다. 이유는 1이 입력되면 배열은 0과 1의 인덱스를 갖는 배열을 생성하게 할텐데, 그럴경우 인덱스 2에 2를 저장한다는 코드에서 에러가 뜨게 되는 것이다.

 

코드를 보자

---

-풀이-

 

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]) % 10007;
		}
		System.out.println(dp[n]);
	}

}

---

-결과-

 

---

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