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

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

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

 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면

그 수열을 바이토닉 수열이라고 한다.

1 5 2 1 4 3 4 5 2 1 을 예로들면 

길이 7의 1 2 3 4 5 2 1 이 정답이 된다. 5를 기준 왼쪽은 증가, 오른쪽은 감수하는 부분수열이다.

 

수열 인덱스 1~N 를 전부 반복문을 돌면서

임의의 한 부분을 최대값으로 잡고 왼쪽 오른쪽에 대한 부분수열을 구해주면 된다.

 

더보기
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> v;
int N, start_num;
int arr[1001];
int Max, cnt;
 
int bound(int s, int e, int key) {
    int m;
    while (s < e) {
        m = (s + e) / 2;
        if (v[m] > key) s = m + 1;
        else e = m;
    }
    return s;
}
 
int setup(int i, int check) {
    if (check) {
        for (int k = i - 1; k >= 0; k--) {
            if (v[v.size() - 1] > arr[k]) {
                v.push_back(arr[k]);
            }
            else {
                int bnd = bound(0, v.size() - 1, arr[k]);
                if (v[bnd] != start_num) {
                    v[bnd] = arr[k];
                }
            }
        }
    }
    else {
        for (int k = i + 1; k < N; k++) {
            if (v[v.size() - 1] > arr[k]) {
                v.push_back(arr[k]);
            }
            else {
                int bnd = bound(0, v.size() - 1, arr[k]);
                if (v[bnd] != start_num) {
                    v[bnd] = arr[k];
                }
            }
        }
    }
    return v.size();
}
 
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    for (int i = 0; i < N; i++) {
        cnt = 0;
        v.clear();
        start_num = arr[i];
        v.push_back(arr[i]);
        cnt += setup(i,1);
 
        v.clear();
        v.push_back(arr[i]);
        cnt += setup(i,0) - 1;
 
        Max = Max < cnt ? cnt : Max;
    }
    cout << Max;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

복습 20.02.09

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

BOJ 1699번 제곱수의 합  (0) 2020.01.07
BOJ 1912번 연속합  (0) 2020.01.07
BOJ 11055번 가장 큰 증가 부분수열  (0) 2020.01.07
BOJ 11053번 가장 긴 증가하는 부분수열  (0) 2020.01.06
BOJ 2156번 포도주 시식  (0) 2020.01.06

+ Recent posts

티스토리툴바