https://www.acmicpc.net/problem/19623

 

회의는 한번에 하나만 진행이 가능하며, 주어지는 N개의 회의들을 적절하게 배정하여 최대 인원을 구하는 문제입니다.

저는 dp + parametric search로 접근했습니다.

dp[N]: N번째 회의부터 모을 수 있는 최대 인원

 

우선 회의들을 시작시간 기준 오름차순으로 정렬합니다.

그리고 해당 회의를 진행하거나, 진행하지 않거나 두가지를 모두 확인할 수 있습니다.

 

이번 회의를 넘긴다면 바로 idx + 1번째 회의로 넘어가면 되고,

이번 회의를 진행한다면 회의가 끝나는 시간을 기준으로 가장 빠르게 시작하는 회의로 넘어갈 수 있습니다.

다음 회의는 파라매트릭 서치를 통해 구할 수 있습니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 100001
using namespace std;
 
typedef struct Node {
    int l, r, s;
}Node;
 
Node list[MAX];
int dp[MAX];
int N;
 
bool cmp(Node a, Node b) {
    return a.l < b.l;
}
 
int bs(int x) {
    int l = 0;
    int r = N;
    while (l < r) {
        int m = (l + r) >> 1;
        if (list[m].l >= x) r = m;
        else l = m + 1;
    }
    return l;
}
 
int solve(int idx) {
    if (idx >= N) return 0;
 
    int& ret = dp[idx];
    if (ret != -1) return ret;
 
    return ret = max(solve(idx + 1), list[idx].s + solve(bs(list[idx].r)));
}
 
void func() {
    sort(list, list + N, cmp);
    memset(dp, -1, sizeof(dp));
    cout << solve(0) << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> list[i].l >> list[i].r >> list[i].s;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 30461 낚시  (0) 2024.07.28
boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29

https://www.acmicpc.net/problem/30461

 

점화식만 구한다면 쉽게 풀리는 문제입니다.

2차원 배열의 누적합이지만 기존 방식처럼 (1, 1) ~ (x, y)의 모든 값을 더하는 것이 아닌 대각선 범위에 있는 수들을 더해야합니다.

 

우선 본인보다 위에 있는 수는 포함되어야 합니다. 그러면 dp[i - 1][j]를 추가합니다.

다음은 본인보다 대각선 위에 있는 수도 포함되어야 합니다. 그러면 dp[i - 1][j - 1]가 추가됩니다.

 

여기서 하나 생각해야할건 dp[i - 1][j]에는 dp[i - 2][j - 1]이 포함되어 있습니다. (대각선)

그리고 dp[i - 1][j - 1]에도 dp[i - 2][j - 1]가 포함되어 있습니다. (위)

그러니 i > 1인 좌표에서는 dp[i - 2][j - 1]를 한번 빼줘야 점화식이 완성됩니다.

 

그러면 최종 점화식은

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] - dp[i - 2][j - 1]

이렇게 됩니다!

점화식을 구했으니 이제 입력이 들어오면 바로 dp[x][y]를 출력해주시면 되겠습니다.

 

 

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
#include <iostream>
#define MAX 2001
using namespace std;
 
int dp[MAX][MAX];
int N, M, Q;
 
void func() {
    int x, y;
    while (Q--) {
        cin >> x >> y;
        cout << dp[x][y] << '\n';
    }
}
 
void input() {
    cin >> N >> M >> Q;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> dp[i][j];
            dp[i][j] += (dp[i - 1][j] + dp[i - 1][j - 1]);
            if (i > 1) {
                dp[i][j] -= dp[i - 2][j - 1];
            }
        }
    }
}
 
int main() {
    cin.tie(nullptr); cout.tie(nullptr);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 19623 회의실 배정 4  (0) 2024.07.29
boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29

https://www.acmicpc.net/problem/17258

 

어디서 많이 본 문제네요!

월클병에 걸려버린 욱제가 파티 인원이 T명 이상일 때만 파티에 참여한다고 합니다.

친구를 최대 K명까지 투입하여 파티에 참여하는 시간을 최대로 만들어야 하는 문제입니다.

그 친구들은 친구들을 제외한 나머지 인원이 T명 이상이면 파티를 모두 나간다고 합니다.

그래서 적절한 시기에 친구들을 투입해야 최대를 구할 수 있습니다.

 

저는 dp를 활용했고, 파티 참여 인원을 구하기 위해 누적합을 추가했습니다.

imos 기법을 활용하여 시작과 끝 지점에만 카운팅을 해주고, 마지막에 누적합을 구해줍니다.

 

dp[N][K][pre]: N 시간에 친구 K명을 부를 수 있고, 파티에 참여중인 친구가 pre명일 때 파티에 머무르는 최대 시간

dp를 이렇게 구성했지만 2차원 배열로도 푸신분이 계시더라고요..? 전 모르겠습니다

 

문제에서 생각해볼 경우들은

1. 누적합이 이미 T 이상인지

2. 이전부터 참여중인 친구들과 합쳐서 T 이상인지

3. 파티를 유지할 수 있도록 친구들이 추가될 수 있는지

이렇게 3가지가 되겠습니다.

 

누적합이 이미 T 이상이라면 파티가 유지될 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이때 친구들을 제외한 인원들이 T 이상이므로 참여하고 있던 친구들은 모두 빠져나갑니다.

 

이전부터 참여중인 친구들과 합쳐서 T 이상이라면 파티가 유지될 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이때 친구들을 제외하면 T보다 작으므로 참여하고 있던 친구들은 계속 참여합니다.

 

파티를 유지할 수 있도록 친구들이 추가될 수 있다면 부족한 인원을 채워줄지, 아니면 친구들을 추가하지 않고 다음 시간을 확인할 지 선택합니다.

친구들을 추가한다면 +1을 해주고, 둘중 최대를 구합니다.

친구를 추가할 수 없다면 다음 시간을 보는것 밖에 없습니다.

 

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 310
using namespace std;
 
int dp[MAX][MAX][MAX];
int sum[MAX];
int N, M, K, T;
 
int solve(int idx, int k, int pre) {
    if (idx == N + 1) return 0;
 
    int& ret = dp[idx][k][pre];
    if (ret != -1) return ret;
 
    if (sum[idx] >= T) {
        return ret = solve(idx + 1, k, 0) + 1;
    }
    if (sum[idx] + pre >= T) {
        return ret = solve(idx + 1, k, pre) + 1;
    }
 
    ret = solve(idx + 1, k, pre);
    int tmp = T - (sum[idx] + pre);
    if (tmp <= k) {
        ret = max(ret, solve(idx + 1, k - tmp, pre + tmp) + 1);
    }
    return ret;
}
 
void init() {
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i < MAX; i++) {
        sum[i] += sum[i - 1];
    }
}
 
void func() {
    init();
    cout << solve(1, K, 0) << '\n';
}
 
void input() {
    int l, r;
    cin >> N >> M >> K >> T;
    while (M--) {
        cin >> l >> r;
        sum[l]++;
        sum[r]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 19623 회의실 배정 4  (0) 2024.07.29
boj 30461 낚시  (0) 2024.07.28
boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29

https://www.acmicpc.net/problem/1398

 

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 ...

위 동전들을 적절히 사용하여 N을 만들기 위한 최소 갯수를 구하는 문제입니다.

 

동전들을 3개씩 끊어본다면

(1, 10, 25)

(1, 10, 25) * 100

(1, 10, 25) * 100 * 100

(1, 10, 25) * 100 * 100 * 100

이런식으로 규칙이 된다는 것을 알 수 있습니다.

그러면 굳이 문제에서 요구하는 큰 범위까지 갈 필요 없이 100 단위로 끊어서 접근한다면 간단하게 해결할 수 있습니다.

 

같은 금액에서의 답은 똑같기 때문에 dp를 사용했습니다.

그리고 dp 배열을 초기화할 필요도 없습니다.

(1, 10, 25) 으로 99원을 만들든, (100, 1000, 2500) 으로 9900원을 만들든 똑같은 결과가 나오기 때문입니다.

여기까지 오셨다면 구현은 간단합니다.

 

 

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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 101
using namespace std;
typedef long long ll;
 
int dp[MAX];
int list[3] = { 1,10,25 };
ll N;
 
int solve(int n) {
    if (!n) return 0;
 
    int& ret = dp[n];
    if (ret != -1) return ret;
 
    ret = 1e9;
    for (int i = 0; i < 3; i++) {
        if (n < list[i]) continue;
 
        ret = min(ret, solve(n - list[i]) + 1);
    }
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    
    int ret = 0;
    while (N) {
        ret += solve(N % 100LL);
        N /= 100LL;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

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

boj 30461 낚시  (0) 2024.07.28
boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28

https://www.acmicpc.net/problem/1229

 

간단한 dp 문제입니다.

문제가 요구하는 육각수들의 수를 미리 구한 다음 N을 만들기 위해 필요한 육각수의 갯수를 구하여 해결할 수 있습니다.

 

육각수의 수는

1 * 1

2 * 3

3 * 5

4 * 7

5 * 9

이렇게 규칙을 찾을 수 있고, An = n * (2n - 1) 으로 구할 수 있습니다.

 

dp[i] = i를 만들기 위해 필요한 육각수의 최소 갯수

인덱스가 갯수이므로 dp[i] = dp[i - 현재 육각수의 갯수] + 1으로 최솟값을 갱신할 수 있습니다.

 

 

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
#include <iostream>
#define MAX_N 1000001
#define MAX_M 710
using namespace std;
 
int list[MAX_M];
int dp[MAX_N];
int N;
 
void init() {
    for (int i = 1; i < MAX_M; i++) {
        list[i] = i * ((i << 1) - 1);
    }
}
 
void func() {
    init();
 
    dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = 1e9;
        for (int j = 1; j < MAX_M; j++) {
            if (i < list[j]) break;
            dp[i] = min(dp[i], dp[i - list[j]] + 1);
        }
    }
 
    cout << dp[N] << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 17258 인기가 넘쳐흘러  (0) 2024.07.20
boj 1398 동전 문제  (0) 2024.07.04
boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27

https://www.acmicpc.net/problem/25378

 

1. 인접한 두 장소에서 임의의 동일한 개수의 조약돌을 가져가기
2. 한 장소에서 임의의 개수의 조약돌을 가져가기

조약돌을 가져갈 수 있는 방법은 이렇게 두가지 입니다.

 

"어떤 장소에 조약돌이 더 이상 없는 경우에도 그 장소는 그대로 남아 있어서, 초기에 인접하지 않았던 두 장소가 인접한 것으로 바뀌지 않는다."

그리고 이렇게 조건도 명시되어 있어서 그 자리에 있는 조약돌은 모두 가져가야 되는것을 알 수 있습니다.

 

dp[i]: i번 위치까지 1번 작업을 통해 줄어든 작업의 최대 횟수

우선 최대 작업 횟수는 N번으로,  모두 2번 방법으로 가져가는 경우입니다.

dp를 구할때는 1번 방법만 사용하기 때문에 앞에서 가져간 이후 몇개가 남았는지 유지하는게 중요합니다.

도중에 r = 0이 되었다면 dp[i - 1] + 1으로 갱신하여 횟수를 줄여주도록 합니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 2501
using namespace std;
 
int dp[MAX];
int list[MAX];
int N;
 
void func() {
    for (int i = 1; i <= N; i++) {
        dp[i] = max(dp[i], dp[i - 1]);
        int r = list[i];
        for (int j = i + 1; j <= N; j++) {
            r = list[j] - r;
 
            if (r < 0) break;
            if (!r) dp[j] = max(dp[j], dp[i - 1] + 1);
        }
    }
 
    cout << N - dp[N] << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 1398 동전 문제  (0) 2024.07.04
boj 1229 육각수  (0) 2024.06.30
boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13

https://www.acmicpc.net/problem/2216

 

같은 위치에 있는 문자를 비교하여 아래와 같이 점수를 받습니다.

1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.

 

여기서 문자 사이에 공백을 원하는대로 넣을수 있기 때문에

적절하게 공백을 넣어서 점수를 최대로 받아야 하는 문제입니다.

 

dp[idx1][idx2]: 문자열을 idx1, idx2까지 사용했을 때 얻을 수 있는 최대 점수

s1, s2 중 하나의 문자에 공백을 추가하거나 두 문자를 비교하여 a, b, c 중 적절한 값을 더합니다.

위 3가지 중 max를 구하도록 합니다.

 

 

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
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#define MAX 3010
using namespace std;
 
string s1, s2;
int dp[MAX][MAX];
int a, b, c;
int len1, len2;
 
int solve(int idx1, int idx2) {
    if (idx1 == len1) return (len2 - idx2) * b;
    if (idx2 == len2) return (len1 - idx1) * b;
 
    int& ret = dp[idx1][idx2];
    if (ret != -1) return ret;
    ret = b + max(solve(idx1 + 1, idx2), solve(idx1, idx2 + 1));
    if (s1[idx1] == s2[idx2]) {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + a);
    }
    else {
        ret = max(ret, solve(idx1 + 1, idx2 + 1) + c);
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << '\n';
}
 
void input() {
    cin >> a >> b >> c >> s1 >> s2;
    len1 = s1.size();
    len2 = s2.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 1229 육각수  (0) 2024.06.30
boj 25378 조약돌  (0) 2024.06.29
boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13

https://www.acmicpc.net/problem/1354

 

  • Ai = 1 (i ≤ 0)
  • Ai = A⌊i / P⌋ - X + A⌊i / Q⌋ - Y (i ≥ 1)

여기에서 An을 구하는 문제입니다.

우선 N이 10^13이기 때문에 단순 배열만으로는 해결할 수 없습니다.

그래서 처음 생각해낸건 map을 사용하여 dp를 해결하려고 했습니다.

 

dp 재귀를 돌릴 때 dp[n] != -1이면 dp[n]을 리턴했던것 처럼

map에 포함되어 있는 수는 이미 방문처리가 되었으므로 그 수를 리턴하도록 합니다.

 

 

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
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
 
unordered_map<ll, ll> m;
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n <= 0) return 1LL;
    if (m.find(n) != m.end()) return m[n];
    return m[n] = solve(n / p - x) + solve(n / q - y);
}
 
void func() {
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

근데 생각보다 메모리를 많이 차지하고, 시간도 많이 소요되는 것을 알 수 있습니다.

다른분들의 제출 현황을 보니 이 방법은 비효율적이라는 것을 알 수 있었습니다.

 

제가 확인해봤던 풀이로는 배열을 활용하는 방법이었습니다.

하지만 N의 범위가 10^13이기 때문에 모든 범위를 배열로 해결할 수는 없습니다.

문제에서 허용하는 메모리 512MB 내에서는 가능하기 때문에 10000000 까지는 배열로, 나머지는 재귀로 해결할 수 있었습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 10000001
using namespace std;
typedef long long ll;
 
ll dp[MAX];
ll N, p, q, x, y;
 
ll solve(ll n) {
    if (n < MAX) return dp[n];
 
    ll l = 1LL;
    if (n / p - x > 0) l = solve(n / p - x);
 
    ll r = 1LL;
    if (n / q - y > 0) r = solve(n / q - y);
 
    return l + r;
}
 
void init() {
    dp[0] = 1LL;
    for (int i = 1; i < MAX; i++) {
        dp[i] = dp[max(0LL, i / p - x)] + dp[max(0LL, i / q - y)];
    }
}
 
void func() {
    init();
    cout << solve(N) << '\n';
}
 
void input() {
    cin >> N >> p >> q >> x >> y;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

 

아까와 비교하면 메모리와 시간 차이가 정말 많이 난다는 것을 알 수 있습니다.

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

boj 25378 조약돌  (0) 2024.06.29
boj 2216 문자열과 점수  (0) 2024.06.28
boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08

https://www.acmicpc.net/problem/3114

 

(1, 1)에서 출발하여 (N, M)에 도착했을 때 사과 + 바나나의 최대를 구하는 문제입니다.

이동은 아래, 오른쪽, 오른쪽 + 아래 만 가능합니다.

 

(x, y) 기준 사과 + 바나나의 합은

1. (x, y) ~ (x - 1, y) 까지는 바나나

2. (x + 1, y) ~ (N, y) 까지는 사과

두개를 더하여 계산합니다.

그렇다면 사과와 바나나의 누적합은 각각 구할 수 있고, 세로별로 누적합을 구하도록 합니다.

 

세팅이 완료되었다면 점화식을 구해봅니다.

이동 가능한 방향이 어떻게 되는지를 이용하면 (x, y) 기준 3개 중 하나를 답으로 가져갈 수 있습니다.

(x - 1, y - 1), (x, y - 1)에서 왔을 경우 y 좌표가 바꼈으므로 이전에 구했던 누적합을 더하면 됩니다.

(x - 1, y)에서 왔을 경우 y좌표가 바뀌지 않았으므로 누적합 범위를 조정해야 합니다.

 

dp 값을 채워나가는 도중에 dp[N][M]보다 커지는 경우가 있을 수 있으니 dp[N][M]를 명시하여 출력해주시면 되겠습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 1501
using namespace std;
 
int sumA[MAX][MAX], sumB[MAX][MAX], dp[MAX][MAX];
int N, M;
 
void func() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (j == 1) {
                dp[i][j] = sumA[N][j] - sumA[i][j];
                continue;
            }
 
            int tmp = sumA[N][j] - sumA[i][j] + sumB[i - 1][j];
            dp[i][j] = max(max(dp[i - 1][j - 1], dp[i][j - 1]) + tmp, dp[i - 1][j] - sumA[i][j] + sumA[i - 1][j]);
        }
    }
 
    cout << dp[N][M] << '\n';
}
 
void input() {
    char ch;
    int x;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> ch >> x;
            if (ch == 'A') {
                sumA[i][j] = x;
            }
            else {
                sumB[i][j] = x;
            }
            sumA[i][j] += sumA[i - 1][j];
            sumB[i][j] += sumB[i - 1][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 2216 문자열과 점수  (0) 2024.06.28
boj 1354 무한 수열 2  (0) 2024.06.27
boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 12841 정보대 등산  (0) 2023.07.31

https://www.acmicpc.net/problem/11560

 

약 1년만에 dp 문제입니다. 그동안 게을러 빠졌었네요 ^^..

 

이 문제는 N, M의 범위가 작으므로 미리 모든 값을 구할 수 있습니다.

그 다음 입력받는대로 출력만 하면 되는 방식입니다.

 

우선 점화식은 N을 직접 늘려가면서 다항식을 구해보시면 충분히 나올 수 있습니다.

 

여기서 알 수 있는 점화식은

i번째 다항식의 j번 계수는 [i - 1번째 다항식]의 [j - i번째 계수] ~ [j번째 계수]까지의 합으로 구할 수 있습니다.

그렇다면 점화식은

dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j - i + 1] + ... + dp[i - 1][j]

이렇게 될 것이고, 코드로 그대로 옮겨주시면 되겠습니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX_N 21
#define MAX_M 211
using namespace std;
typedef long long ll;
 
ll dp[MAX_N][MAX_M];
int N, M;
 
void init() {
    dp[1][0] = 1LL;
    dp[1][1] = 1LL;
    for (int i = 2; i < MAX_N; i++) {
        for (int j = 0; j <= (i * (i + 1)) >> 1; j++) {
            for (int k = max(0, j - i); k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
}
 
void func() {
    cout << dp[N][M] << '\n';
}
 
void input() {
    cin >> N >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}
 cs

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

boj 1354 무한 수열 2  (0) 2024.06.27
boj 3114 사과와 바나나  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21

https://www.acmicpc.net/problem/28018

 

28018번: 시간이 겹칠까?

댓글을 달아준 학생 수 $N$이 주어진다. $(1\leq N\leq 100\,000)$ 다음 $N$개 줄에는 각 학생의 좌석 배정 시각 $S$와 종료 시각 $E$가 주어진다. $(1\leq S\leq E\leq 1\,000\,000)$ 다음 줄에는 특정한 시각의 개수

www.acmicpc.net

특정 시간에 학생이 몇명 채워져 있는지 구하는 문제입니다.

이 문제는 학생들이 머무르는 구간 l ~ r이 주어집니다.

l ~ r 구간을 모두 채워주어야 하며, 매 쿼리의 l ~ r 구간의 누적을 구하면 O(N^2)의 시간이 걸려 TLE가 발생합니다.

매 쿼리마다 누적합을 갱신하지 않고, 시작과 끝에만 표시하여 한꺼번에 누적합을 구할 수 있는 imos 기법을 활용합니다.

 

학생은 l 시간에 들어와서 r 시간까지 머무릅니다.

따라서 학생이 존재하기 시작하는 l 시간에 +1, 학생이 없는 시간인 r + 1 시간에 -1을 누적합니다.

마지막에 누적합을 갱신하면 O(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
#include <iostream>
#define MAX 1000001
using namespace std;
 
int dp[MAX];
int N, M;
 
void func() {
    for (int i = 1; i < MAX; i++) {
        dp[i] += dp[i - 1];
    }
 
    int x;
    cin >> M;
    while (M--) {
        cin >> x;
        cout << dp[x] << '\n';
    }
}
 
void input() {
    int l, r;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> l >> r;
        dp[l]++;
        dp[r + 1]--;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 3114 사과와 바나나  (0) 2024.06.13
boj 11560 다항식 게임  (0) 2024.06.13
boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26

https://www.acmicpc.net/problem/12841

 

12841번: 정보대 등산

숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다. 정보 과학관을

www.acmicpc.net

출발 지점은 왼쪽, 도착 지점은 오른쪽에 있으므로 무조건 횡단보도를 건너야 합니다. 

문제에서는 1번만 횡단보도를 건널 수 있다고 제한하고 있습니다.

그렇게 되면 계산은 간단해집니다.

왼쪽 길로 가다가 횡단보도를 건너고 나머지는 오른쪽 길로만 간다는 뜻이 됩니다.

 

여기서 누적 합을 떠올릴 수 있습니다.

왼쪽, 오른쪽 길의 누적합을 각각 구합니다.

아래 코드에서는 i + 1번 지점까지의 거리를 dp[i]로 저장하고 있습니다.

따라서 i번 지점에서 횡단보도를 건너려면 dp[i - 1] 까지만 계산하면 됩니다.

dp[i - 1].first + cross[i]: 왼쪽에서 i번 지점까지 이동 후 횡단보도를 건넜을 때의 길이가 됩니다.

 

횡단보도를 건넜으니 이제 오른쪽 길에 위치해 있습니다.

따라서 N번 지점까지 그냥 가기만 하면 됩니다. (+ dp[N - 1].second - dp[i - 1].second)

 

거리가 같으면 번호가 낮은 지점을 출력해야 한다는 점만 주의하셔서 최소를 갱신해주시면 됩니다.

 

 

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
#include <iostream>
#define MAX 100001
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
 
pii dp[MAX];
ll cross[MAX];
int N;
 
void func() {
    int idx = 0;
    ll ret = 1e12;
    for (int i = 1; i <= N; i++) {
        ll sum = cross[i] + dp[i - 1].first + dp[N - 1].second - dp[i - 1].second;
        if (ret > sum) {
            idx = i;
            ret = sum;
        }
    }
 
    cout << idx << ' ' << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> cross[i];
    }
 
    for (int i = 1; i < N; i++) {
        cin >> dp[i].first;
        dp[i].first += dp[i - 1].first;
    }
 
    for (int i = 1; i < N; i++) {
        cin >> dp[i].second;
        dp[i].second += dp[i - 1].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 11560 다항식 게임  (0) 2024.06.13
boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29

+ Recent posts

티스토리툴바