BOJ : https://www.acmicpc.net/problem/1720
github : https://github.com/junho0956/Algorithm/blob/master/1720/1720/%EC%86%8C%EC%8A%A4.cpp
타일맞추는거 정말어렵습니다. 진짜 너무 어렵네요
타일을 맞출 수 있는 모든 가지의 수는 쉽게 구할 수 있습니다.
문제의 조건은 중복되는 수는 2가 아닌 1로 즉, 중복되는 수를 감소시켜야 되는 문제입니다.
대체 어떻게 중복되는 수를 찾아야되는지 고민했습니다.
식을 이렇게 세워봤습니다.
중복되는 수를 A, 중복되지 않는 수를 B라고 했을 때
원하는 답 : 2A + B - A = A+B
즉 2A+B 에서 A+B 를 만들어야하는 문제였습니다. -A 를 어떻게 찾아야되는지 계속 고민했습니다.
결국 실패했고,, 다른 방법을 찾은게 B 즉, 중복되지 않는 수를 찾아보는 것이였습니다.
2A+B+B / 2 = A+B 이니 원하는 답은 같으니까요
중복되지 않는 수는 의외로 쉽게 구할 수 있었습니다.
중복되지 않는 수는 즉 순대칭? 같은 배열을 뜻합니다. 그렸을 때 딱 1번만 보여지는 배열 즉,
예를 들면 가로*세로 기준 2*1 로만 쭉 채운 모양을 말합니다.
이때 중복되지 않는 수는 N이 짝수일때와 홀수일때로 나눌 수 있습니다.
가장 먼저 제 코드에서 아셔야 하는 것은 dp의 값 상태입니다.
저는 재귀로 dp를 해결하는 것을 좋아해서 다른분들과는 반대로 dp[0]이 최종값을 의미하게 됩니다.
dp[0] = 재귀... = 재귀... 이런 형태를 띄게되니까요
N이 홀수일 경우를 먼저 고려해보면,
만약 N이 5이면 순대칭? 을 만들기 위해서는 2부분에 2*1 타일을 넣고 나머지 0~1 부분에 아무거나 넣는것입니다.
즉 N이 홀수일 경우 순대칭배열은 dp[N/2-1] 경우의수입니다.
즉 제 코드 기준으로는 dp[0]이 dp[N]이 되니 순서가 바뀐다는 것을 생각해서
(dp[0]+dp[N/2+1]) / 2 가 N이 홀수일 경우 (2A+B+B)/2 = answer를 만드는 공식이 됩니다.
N이 짝수일 경우를 고려해보면,
만약 N이 6이면 순대칭? 을 만들기 위해서는 2가지 경우가 존재하게 됩니다.
1) N/2를 정확히 나눠서 N/2-1, N/2+1에는 2*1 타일을 넣는 경우
2) (N/2-1)~(N/2+1) 에 1*2 | 2*2 타일을 넣는 경우가 됩니다.
dp[n] 을 길이 n까지 타일을 넣을 수 있는 모든 경우의 수라고 가정하면,
dp[n] = dp[n-1]+dp[n-2] (즉, 길이가 1 적을때와 2 적을때의 모든 경우) 가 된다는 것을 안다면
N이 짝수일 경우 순대칭배열은 dp[N/2]+dp[N/2-1] = dp[N/2+1] 이 되게 되고
제 코드 기준상 반대로 뒤집으면 dp[N/2-1] 이 되게 됩니다.
(dp[0]+dp[N/2-1]) / 2 가 N이 짝수일 경우 (2A+B+B)/2 = answer를 만드는 공식이 됩니다.
|
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
33
34
35
|
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
ll dp[31];
int N;
ll solve(int x) {
if (x > N) return 0;
if (x == N) return 1;
ll& res = dp[x];
if (res) return res;
res = solve(x + 1) + solve(x + 2)*2;
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> N;
ll ans = solve(0);
if (N % 2) {
ans = (dp[0] + dp[N / 2 + 1]) / 2;
if (N == 1) ans = 1;
}
else {
ans = (dp[0] + dp[N / 2 - 1]) / 2;
}
cout << ans;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
'algorithm > BOJ' 카테고리의 다른 글
| BOJ 1213번 팰린드롬 만들기 (0) | 2020.02.16 |
|---|---|
| 1254번 팰린드롬 만들기 (0) | 2020.02.16 |
| BOJ 11060번 점프 점프 (0) | 2020.02.13 |
| BOJ 1890번 점프 (0) | 2020.02.13 |
| BOJ 9184번 신나는 함수 실행 (0) | 2020.02.13 |