BOJ : https://www.acmicpc.net/problem/2133

GitHub : https://github.com/junho0956/Algorithm/blob/master/2133/2133/%EC%86%8C%EC%8A%A4.cpp

잘 정리된 블로그가 있어 주소를 남겨봤습니다. https://mizzo-dev.tistory.com/entry/baekjoon2133

 

타일채우기 문제에는 특정한 규칙이 있습니다.

1. 2*1, 1*2 형식의 짝수형 타일이므로 N이 홀수가 되면 빈공간이 생겨 채울수 없는 문제가 발생합니다.

2. 짝수개(2)씩 늘어나는 타일채우기형이므로 짝수+짝수를 하게되면 중간부분에 특정모양이 새로 생기게 됩니다.

 

3*2 와 3*4 의 그릴 수 있는 형태만 그려보면 3*6, *8, *10,

이렇게 짝수개로 늘어날때 2개씩 특정모양이 생기게 됨을 알 수 있습니다.

3*2 를 3개로 기본값을 보고

3*4 를 채우기 위해서는 (3*2) * (3*2) + (3*4)의 고유모양 2개 = 9+2 = 11

3*6 를 채우기 위해서는 (3*2) * (3*4) + (고유모양 3*4)*(3*2) 개 + (3*6)의 고유모양 2개 = 33 + 6 + 2 = 41

3*8 를 채우기 위해서는 (3*2) * (3*6) + (고유모양 3*4)*(3*4) 개 + (고유모양 3*6) * (3*2) 개 + (3*8)의 고유모양 2개

123+25+6+2 = 153 이 됨을 알 수 있습니다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
int N;
int dp[31] = { 1,0,3, };
 
int main() {
    cin >> N;
 
    if (N % 2) cout << "0";
    else {
        for (int i = 4; i <= N; i = i + 2) {
            int temp = dp[2] * dp[i - 2];
            for (int k = 4; k <= i; k=k+2) {
                temp += 2 * dp[i - k];
            }
            dp[i] = temp;
        }
        cout << dp[N];
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2225번 합분해  (0) 2020.01.09
BOJ 9461번 파도반 수열  (0) 2020.01.09
BOJ 11726 2*N 타일링  (0) 2020.01.09
BOJ 1699번 제곱수의 합  (0) 2020.01.07
BOJ 1912번 연속합  (0) 2020.01.07

BOJ : https://www.acmicpc.net/problem/11726

GitHub : https://github.com/junho0956/Algorithm/blob/master/11726/11726/%EC%86%8C%EC%8A%A41.cpp

 

2*N 타일링을 처음 풀었을 때는

이걸 어떻게 하나 했는데 손으로 작성해보니 피보나치와 같은 값을 가진다는 것을 알고 해결했었다.

그냥 규칙찾는 문제인줄 알았는데 다른 타일링 문제를 풀면서

타일링 문제를 제대로 푸는 방법을 알게 되었고

타일링문제의 기본인 2*N 타일링을 다시 풀어보았다.

여러 타일링 문제에 접목시킬 수 있는 가장 기본기 인 것 같다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
#define MOD 10007
int N;
int dp[1001];
 
int solve(int len) {
// 0 미만이라면 가질 수 있는 값이 없다. ex) 1 계산시 알게됨
    if (len < 0) return 0;
// 0 과 1 이라면 1이라는 값을 가질 수 있다.
    if (len <= 0) return 1;
 
    if (dp[len]) return dp[len];
 
// 가로로 1칸을 준 경우 + 세로로 2칸을 준 경우
    dp[len] = (solve(len - 1) + solve(len - 2)) % MOD;
    return dp[len];
}
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> N;
    cout << solve(N);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 9461번 파도반 수열  (0) 2020.01.09
BOJ 2133번 타일채우기  (0) 2020.01.09
BOJ 1699번 제곱수의 합  (0) 2020.01.07
BOJ 1912번 연속합  (0) 2020.01.07
BOJ 11054번 가장 긴 바이토닉 부분수열  (0) 2020.01.07

BOJ : https://www.acmicpc.net/problem/1699

GitHub : https://github.com/junho0956/Algorithm/blob/master/1699/1699/%EC%86%8C%EC%8A%A4.cpp

 

 

1부터 N까지 모두 제곱수의 합으로 나타낼 수 있다.

 

먼저 dp[i]는 i를 제곱수의 합으로 나타내는 경우라고 할 때

1로 i를 구성한다면 기본 갯수는 i가 된다.

 

그리고 1부터 시작해서 어떤 수를 제곱했을 때 i에 가장 가까운 수를 k*k이라고 했을 때

점화식은 dp[i]=min(dp[i],dp[i-k*k]+1) 이 될 것이다.

 

ex) dp[4]의 경우

dp[4] = min(dp[4], dp[4-1*1]+1) <= 현재 dp[4] 는 4, dp[4-1*1] + 1 => dp[3]+1 = 4 같음

dp[4] = min(dp[4], dp[4-2*2]+1) <= 현재 dp[4] 는 4, dp[4-2*2] + 1 => dp[0]+1 = 1 갱신

 

 

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[100001];
int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    
    for (int i = 1; i <= n; i++) {
        dp[i] = i;
 
        for (int k = 1; k * k <= i; k++) {
            dp[i] = min(dp[i], dp[i - k*k] + 1);
        }
    }
    cout << dp[n];
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

 

 

복습 20.02.09 재귀로 해결!

그런데 시간차이가 심하다. .. ...

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2133번 타일채우기  (0) 2020.01.09
BOJ 11726 2*N 타일링  (0) 2020.01.09
BOJ 1912번 연속합  (0) 2020.01.07
BOJ 11054번 가장 긴 바이토닉 부분수열  (0) 2020.01.07
BOJ 11055번 가장 큰 증가 부분수열  (0) 2020.01.07

BOJ : https://www.acmicpc.net/problem/1912

GitHub : https://github.com/junho0956/Algorithm/blob/master/1912/1912/%EC%86%8C%EC%8A%A4.cpp

 

연속 수열로 부분 합을 만들어가려면

당장 현재 값이 더 커서 현재값만 넣거나

현재값에 이전값들의 합만 넣거나 둘중 하나가 된다.

 

=> dp[i] = max(arr[i], dp[i-1]+arr[i])

 

더보기
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
#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[100001];
int arr[100001];
int n;
 
int main() {
    ios::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    int Max;
    Max = dp[0] = arr[0];
 
    for (int i = 1; i < n; i++) {
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
        Max = max(Max, dp[i]);
    }
    cout << Max;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11726 2*N 타일링  (0) 2020.01.09
BOJ 1699번 제곱수의 합  (0) 2020.01.07
BOJ 11054번 가장 긴 바이토닉 부분수열  (0) 2020.01.07
BOJ 11055번 가장 큰 증가 부분수열  (0) 2020.01.07
BOJ 11053번 가장 긴 증가하는 부분수열  (0) 2020.01.06

+ Recent posts

티스토리툴바