Algorithms
[백준 알고리즘] (DP) 11727번 Java 풀이
SDev
2020. 3. 11. 20:13
728x90
DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052
출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]
change Nxxxx -> Main && remove package lines!!!
이클립스에서 작성하면서 문제 이름으로 클래스를 생성하여 풀었기 때문에
클래스 이름을 Main으로 바꾸고, package 부분도 지우고 제출해야 정상적으로 돌아갑니다.
<풀이> - Bottom up
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
|
package dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class N11727 {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int d[] = new int[n+1];
for(int i=0; i<n+1; i++) {
if(i ==1) {
d[i] = 1;
}else if(i ==2){
d[i] = 3;
}else if(i>=3){
d[i] = d[i-1] + 2*(d[i-2]);
d[i] %=10007;
}
}
System.out.println(d[n]);
}
}
Colored by Color Scripter
|
<풀이> - Top down
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
32
|
package dp;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class N11727_TD {
public static int d[];
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
int n = Integer.parseInt(br.readLine());
d = new int[n+1];
System.out.println(calc(n));
}
public static int calc(int n) {
if(n ==0 || n ==1) return 1;
if(d[n]>0) return d[n];
d[n] = 2 *calc(n-2) + calc(n-1);
d[n] %= 10007;
return d[n];
}
}
Colored by Color Scripter
|
이와 같은 DP문제 풀이에서 핵심 부분은 점화식을 구하는 과정인데,
이 문제의 경우 11726번 문제에서 2*2 의 타일이 더해진 형식입니다.
2*2타일로 인해 누운 타일이 2개 추가되는 d[n-2]가 2개 있는 것과 같습니다.
Github: https://github.com/jaeuk9407/AlgorithmBOJ
jaeuk9407/AlgorithmBOJ
BaekJoon Online Judge Problems. Contribute to jaeuk9407/AlgorithmBOJ development by creating an account on GitHub.
github.com