-
[알고리즘-JAVA] 백준 알고리즘 11727번 - 2*n 타일링 2알고리즘 2019. 8. 1. 02:12
접근 과정
1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?2*n 직사각형을 2*1, 1*2, 2*2 타일로 채우는 방법의 수를 구하는 문제이다.
2. 나의 방식대로 문제를 재정의 하자.
d[n] = 2*n 직사각형을 타일로 채우는 방법의 수.d[n]을 점화식 형태로 표현해 내기.
3. 어떤 알고리즘과 자료구조를 사용할 것인가?재귀함수 (Top-down)이나 반복문(Bottom-UP)을 사용할 계획이다.
4. 어떻게 계산할 것인가?
1) 입력BufferedReader를 사용해 입력받을 것이다.
2) 시간 복잡도 계산
최악 = O(N) (d[n]까지 n번 계산)
5. 주의할 점은 무엇인가?
방법의 수를 10007로 나눈 나머지를 구해야한다.
6. 풀이 과정
전체 소스 코드
Top-Down
크게 달라진건 없고, 이전 2*n 문제에서
d[length] = calculate(length-2)블럭이 하나 더 추가되었다는 점이다.
length-2인 이유는 2*2 블럭이기 때문에 왼쪽에 남는 여백의 가로길이가 n-2이기 때문이다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main{ static long d[]; public static void main(String args[]) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int length = Integer.parseInt(bf.readLine()); d = new long[length+1]; System.out.println(calculate(length)); }; static long calculate(int length){ if (length == 0 || length == 1){ return 1; } if (d[length] > 0) return d[length]; // calculate(length-2) 하나 더 추가 for 2*2 block d[length] = calculate(length-1) + calculate(length-2) + calculate(length-2); d[length] %= 10007; return d[length]; } }
Bottom-Up
이 역시 크게 달라진 것 없이 d[length]를 구하는 부분을 추가해 주면 된다.
아래의 코드를 보면 d[i] = d[i-1] + d[i-2] + d[i-2]로 구하는 것을 알 수 있다.
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main{ public static void main(String args[]) throws IOException{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int length = Integer.parseInt(bf.readLine()); //bottom-up int d[] = new int[length+1]; d[0] = 1; d[1] = 1; for (int i = 2; i <= length; i++){ // 추가된 부분 : d[i-2] for 2*2 block d[i] = d[i-1] + d[i-2] + d[i-2]; d[i] %= 10007; } System.out.println(d[length]); }; }
'알고리즘' 카테고리의 다른 글
[알고리즘-JAVA] 백준 알고리즘 11052번 - 카드 구매하기 (0) 2019.08.02 [알고리즘-JAVA] 백준 알고리즘 9095번 - 1, 2, 3 더하기 (0) 2019.08.01 [알고리즘-JAVA] 백준 알고리즘 11726번 - 2*n 타일링 (0) 2019.08.01 [알고리즘-JAVA] 백준 알고리즘 1463번 - 1로 만들기 (2) 2019.07.31 [알고리즘-JAVA] 다이나믹 프로그래밍 (0) 2019.07.31