[백준] 11727 - 2×n 타일링 2 (JAVA)

1. 소요시간 : 10분
2. 문제 사이트 : 백준
3. 문제 수준 : 실버 3
4. 문제 유형 : 다이나믹 프로그래밍
5. 다른 사람의 풀이를 참고 했는가 ? : X
6. 한 번 풀었다가 다시 푸는 문제인가 ? : O
7. 문제 링크 : https://www.acmicpc.net/problem/11727
8. 푼 날짜 : 2023.03.19

1. 사용한 자료구조 & 알고리즘

다이나믹 프로그래밍을 사용했다.

2. 사고과정

문제를 보자마자 다이나믹 프로그래밍이라는 것을 알았고, 규칙을 찾기 위해 직접 경우의 수들을 그려봄으로써 규칙을 찾을 수 있었다. 4개 까지 그렸을 때 규칙을 찾았다.

3. 풀이과정

규칙은 dp[i]=dp[i-2] x 2 + dp[i-1] 이다.
예를 들어 dp[3] = dp[1] x 2 + dp[2] = 5
dp[4] = dp[2] x 2 + dp[3] = 11

4. 소스코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n=Integer.parseInt(br.readLine());
		int dp[]=new int[1001];
		dp[1]=1;
		dp[2]=3;
		for(int i=3;i<dp.length;i++) {
			dp[i]=(dp[i-2]*2+dp[i-1])%10007;
		}
		System.out.println(dp[n]);
		
		
		
	}
}

5. 결과

1달만에 다시 푸는 문제였다.

6. 회고

오늘부터 내게 가장 부족한 부분인 DP를 집중적으로 공부할 것이다.
파이팅!

하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212