-
[백준/BOJ] 11727번 : 2Xn 타일링 2 (JAVA / 자바)백준 2022. 3. 23. 21:25
안녕하세요~ 코딩하는 코알못 코메인입니다.
https://www.acmicpc.net/problem/11727
- 문제 -
난이도 실버 3 문제이다.
자바에서 입력방식은 scanner와 bufferedreader가 있다.
자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.
bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.
더 자세한 내용은 아래 글 참고 하면 좋다.
풀이 방법
https://comain.tistory.com/303
이름처럼이나 매우 비슷한 문제이다. 같은 점화식이지만 패턴이 좀 다르다.
일단 쉽게 가짓수를 구할 수 있는데까지 구해보자.
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]); } }
-결과-
아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.
'백준' 카테고리의 다른 글
[백준/BOJ] 17626번 : Four Squares (JAVA / 자바) (0) 2022.03.25 [백준/BOJ] 18870번 : 좌표 압축 (JAVA / 자바) (0) 2022.03.24 [백준/BOJ] 11726번 : 2Xn 타일링 (JAVA / 자바) (0) 2022.03.23 [백준/BOJ] 11724번 : 연결 요소의 개수 (JAVA / 자바) (0) 2022.03.22 [백준/BOJ] 1748번 : 수 이어 쓰기 1 (JAVA / 자바) (0) 2022.03.21