[BaekJoon] 1309번 - 동물원 [Java][C++]
1. 문제 풀이
$2 \times N$ 크기의 배열에 사자들을 배치해야 하는데 이때 사자들이 가로로도 세로로도 붙어 있게 배치할 수 없다. 이때 배치할 수 있는 모든 경우의 수를 세야하며 사자를 한 마리도 배치하지 않는 경우도 하나의 경우로 센다.
해당 문제는 다이나믹 프로그래밍을 활용하면 해결할 수 있는데 현재 사자를 배치하려는 열 번호를 $i$ 라고 했을 때, 해당 열에 사자를 배치하지 않는 경우의 수는 이전 열인 $i-1$ 번째 열에 사자를 배치하거나 배치하지 않은 경우의 수의 합이다. 현재 열에 사자를 배치하는 경우의 수는 이전 열인 $i-1$ 번째 열에서 사자를 배치하지 않았을 경우 윗 칸 또는 아랫 칸에 배치할 수 있고, 사자를 배치했을 경우 배치한 칸의 대각선 칸에 배치할 수 있다.
즉 사자를 배치하지 않는 경우의 수를 $a$, 사자를 배치하는 경우의 수를 $b$ 라고 할 때, 열 $i$ 에 사자를 배치하지 않는 경우 수는 $a_i = a_{i-1} + b_{i-1}$ 이며, 열 $i$ 에 사자를 배치하는 경우의 수는 $b_i = 2 \times a_{i-1} + b_{i-1}$ 이 된다.
2차원 dp 테이블을 활용해 점화식대로 구현해도 되고, 이전 상태만 필요하면서 행이 2개뿐이라 그냥 변수로 처리해서 메모리 최적화를 해도 된다.
2. 코드
1. Bottom-Up 2차원 dp [Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.io.*;
public class Main {
static int MOD = 9901;
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[1 + N][2];
dp[0][0] = 1;
for (int i = 1; i <= N; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
dp[i][1] = (2 * dp[i - 1][0] + dp[i - 1][1]) % MOD;
}
System.out.println((dp[N][0] + dp[N][1]) % MOD);
}
}
2. Bottom-Up 2차원 dp [C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 9901;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> dp(1 + n, vector<int>(2));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
dp[i][1] = (2 * dp[i - 1][0] + dp[i - 1][1]) % MOD;
}
cout << (dp[n][0] + dp[n][1]) % MOD;
}
3. 메모리 최적화 [Java]
for 문에서 skip 변수 갱신 후 take 변수를 갱신하는데 이때 take 변수의 skip은 갱신되기 이전 값이어야 하므로 prev에 미리 복사해두었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.io.*;
public class Main {
static int MOD = 9901;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int skip = 1;
int take = 0;
for (int i = 0; i < N; i++) {
int prev = skip;
skip = (skip + take) % MOD;
take = (2 * prev + take) % MOD;
}
System.out.println((skip + take) % MOD);
}
}
4. 메모리 최적화 [C++]
for 문에서 skip 변수 갱신 후 take 변수를 갱신하는데 이때 take 변수의 skip은 갱신되기 이전 값이어야 하므로 prev에 미리 복사해두었다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 9901;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int skip = 1;
int take = 0;
for (int i = 0; i < n; i++) {
int prev = skip;
skip = (skip + take) % MOD;
take = (2 * prev + take) % MOD;
}
cout << (skip + take) % MOD;
}