✨ 알고리즘 분류 : 다이나믹프로그래밍
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net

🪡 문제에서 요구하는 조건 정리
- 직사각형 타일 1x2 와 2x1 이 채우는 방법의 수를 구하기
- 출력할 때는 10,007을 나눈 나머지를 출력
🧶 풀이과정
DP는 진짜 나는 어려워서 생각을 많이 해야 했다.
보통 이런 것은 그려보면서 생각을 하는데, 여기에서 같은 점과 계산할 수 있는 부분을 추론하면서 진행을 하게 된다.
이 문제 같은 경우에는
전까지 만들어놓은 타일에서 언제나 현재 n의 자리에서 -1과 -2의 합이 유지된다.
그러니까, -1은 세로 타일이 들어가는 만큼을 추가하는 거고, 2는 가로 타일을 추가하는 것을 생각하면 된다.
세로로 배치하는 타일은 1의 자리를 차지하기 때문에 n-1의 값과 같고
가로로 배치하는 타일은 2의 자리를 차지하기 때문에 n-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[1001];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
}
System.out.println(dp[n]);
br.close();
}
}
'Algorithm' 카테고리의 다른 글
| [058] 9095. 1,2,3 더하기 (1) | 2024.04.12 |
|---|---|
| [057] 11727. 2xn 타일링 2 (0) | 2024.04.12 |
| [055] 1463. 1로 만들기 (0) | 2024.04.09 |
| [054] 2004. 조합 0의 개수 (0) | 2024.04.09 |
| [053] 1676. 팩토리얼 0의 개수 (0) | 2024.04.08 |