문제설명
입력 & 출력
나의 풀이
이번 문제는 2xn 타일링 문제에 이어지는 문제입니다.
위 그림과 같은 타일이 존재할 때 입력으로 n을 받아 2xn의 크기의 직사각형을 채우는 문제입니다.
타일을 채우다 보면 n = 5일 때 0~5까지의 타일링의 수는 다음과 같습니다.
- n= 0 ➡️ 1 (채우는 방법이 없으므로 1부터 시작)
- n= 1 ➡️ 1
- n= 2 ➡️ 3
- n= 3 ➡️ 5
- n= 4 ➡️ 11
- n= 5 ➡️ 21
위 타일링의 수를 생각해서 DP의 가장 핵심요소인 점화식을 도출해야 합니다.
좀 더 이해를 하기 쉽게 그림으로 표현하면 다음과 같습니다.
만약에 n = 3일 때를 보면
- n-1의 타일에서 2x1의 타일이 추가된 것을 볼 수있습니다.
- n-2의 타일에서 2x2를 채우는 경우는
- 1x2 ➡️ 2개
- 2x2 ➡️ 1개
2x1 ➡️ 2개- 2x1의 타일을 2개를 배치하여 2x2를 채울 수도 있지만 이는
n-1에서 이미 사용되었기 때문에 제외합니다. - 따라서 2x2를 공간을 채우는 타일은 무조건 2가지 경우입니다.
- 2x1의 타일을 2개를 배치하여 2x2를 채울 수도 있지만 이는
따라서 점화식은 𝑑𝑝[𝑛]=𝑑𝑝[𝑛−1]+2 ×𝑑𝑝[𝑛−2]입니다.
점화식을 구했다면, 초기값을 세팅한 후 dp배열을 작성하면 됩니다.
이때 n이 2보다 작은 경우에는 dp [2]에 접근하지 않도록 하여 ArrayIndexOutOfBoundsException와 같은 예외가 발생하지 않도록 합니다.
참고❗️
[JAVA] 입출력, BufferedReader, StringTokenizer, StringBuilder 알아보기
Java로 코딩테스트를 보거나 입력을 사용해야 할 때 Scanner 클래스를 사용하면 편리하지만 속도가 느리다는 단점이 있습니다. 그렇기 때문에 속도가 빠른 BufferReader 클래스를 사용을 하면 시간복
pixx.tistory.com
[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기
동적 계획법 DP란❓ 동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임 중 하나로 1940년대 리처드 벨만이 사용하던 용어입니다. 주로 줄여서 DP라고 많이 말하며, 주
pixx.tistory.com
'Coding Test > 백준' 카테고리의 다른 글
[백준] 구간 합 구하기 4 (누적 합, 구간 합, Prefix Sum, 11659번, Java) (0) | 2024.07.18 |
---|---|
[백준] 균형잡힌 세상 (Stack, 스택, toCharArray, 4949번, Java) (0) | 2024.07.17 |
[백준] 듣보잡 (HashSet, HashMap, getOrDefault, contains, sort, 1764번, Java) (0) | 2024.07.16 |
[백준] 색종이 (구현, 2차원 배열, BufferReader, 2563번, Java) (1) | 2024.07.16 |
[백준] 요세푸스 문제 (큐, Queue, BufferReader, 1158번, Java) (0) | 2024.07.15 |