Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- geometry
- array
- SQL
- Data Structure
- Number Theory
- 파이썬
- java
- dynamic programming
- Binary Tree
- Binary Search
- greedy
- Math
- bit manipulation
- 구현
- Counting
- simulation
- Matrix
- Class
- sorting
- Stack
- two pointers
- 자바
- database
- string
- 코테
- implement
- 코딩테스트
- hash table
- Method
- Tree
Archives
- Today
- Total
코린이의 소소한 공부노트
[백준 온라인 저지] 2133. 타일 채우기 본문
3*n 크기의 직사각형을 1*2, 2*1 타일로 채우려고 한다.
1. 입력
- 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 30)
- n이 직사각형의 가로다.
2. 출력
- 첫째 줄에 경우의 수를 출력한다.
3. 예제
4. 코드
1) 잘 안풀려서 제시된 c++ 코드를 java로 바꿔서 돌려본 코드
import java.util.*;
class Main{
public static void main(String[] args){
int n = new Scanner(System.in).nextInt();
int[] d = new int[n+1];
System.out.print(dp(n, d));
}
static int dp(int x, int[] d){
if(x%2==1) return 0;
if(x==0) return 1;
if(x==2) return 3;
if(d[x]!=0) return d[x];
d[x] = 3*dp(x-2, d);
for(int i=4 ; i<=x ; i+=2)
d[x] += 2*dp(x-i, d);
return d[x];
}
}
- 가로를 n-2까지 채웠다고 했을 때 나머지 2를 채우는 경우의 수는 3가지가 있고, n이 4 이상일 때 2의 배수일때마다 고유한 모양이 2가지가 나타난다.
- 따라서 점화식을 쓰면 d[i] = 3*d[i-2] + 2*(d[i-4] + d[i-6] + ... + d[0])
2) 재귀 함수 없이 구현한 코드
import java.util.*;
class Main{
public static void main(String[] args){
int n = new Scanner(System.in).nextInt();
if(n%2==1) System.out.print(0);
else{
int[] d = new int[n+1];
d[0] = 1; d[2] = 3;
for(int i=4 ; i<=n ; i+=2){
d[i] = 3*d[i-2];
for(int j=4 ; j<=i ; j+=2)
d[i] += 2*d[i-j];
}
System.out.print(d[n]);
}
}
}
- 메모리는 1번보다 아주 약간 더 사용했지만 속도도 그만큼 빨라졌다.
'코딩테스트 풀이 > JAVA' 카테고리의 다른 글
[LeetCode/Easy] 1018. Binary Prefix Divisible By 5 (0) | 2023.06.07 |
---|---|
[백준 온라인 저지] 14852. 타일 채우기 3 (0) | 2023.06.07 |
[LeetCode/Easy] 1002. Find Common Characters (0) | 2023.06.06 |
[LeetCode/Easy] 999. Available Captures for Rook (0) | 2023.06.06 |
[LeetCode/Easy] 965. Univalued Binary Tree (0) | 2023.06.06 |