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

 

생애 첫 루비문제입니다.

애드혹 문제라서 그런지 백준 게시판이나 블로그에서 아이디어를 얻지 않았다면 절대 손도 못댈거같은 그런 문제였습니다..

 

제가 힌트를 얻은건 1 ~ N번째 수를 계속 이어붙였을 때 음수 누적합이 나오는 갯수를 구하는 것이었습니다.

사실상 문제의 모든것 이었습니다..

 

아무튼 저는 누적합으로 접근했고, 각 은행들은 원형으로 배치되어 있기때문에 1 ~ N이 아닌 1 ~ 2N의 누적합으로 구해줍니다.

그리고 1, 2, 3, ... N에서 시작하여 N개의 수를 계속 이어붙일 때의 누적합들 중에 음수가 몇번 나오는지 카운팅하면 그게 답입니다.

 

4
1 -2 -1 3

예시로 설명드리면

처음 1번부터 누적합을 쭉 구하면

1 -1 -2 1 / 2 0 -1 2 / 3 1 0 3

이렇게 되고, 음수의 갯수는 3개입니다.

그리고 이후에 배열을 계속 이어도 음수가 나오지 않습니다.

 

그 다음 2번부터 누적합을 구하면

x -2 -3 0 1 / -1 -2 1 2 / 0 -1 2 3

이렇게 되고, 음수의 갯수는 5개입니다.

 

다음 3번부터 누적합을 구하면

x x -1 2 3 1 / 0 3 4 2 / 1 4 5 3

이렇게 되고, 음수의 갯수는 1개입니다.

 

마지막 4번부터 누적합을 구하면

x x x 3 4 2 1 / 4 5 3 2 / 5 6 4 3

이렇게 되고, 음수의 갯수는 0개입니다.

위에서 구한 갯수들을 전부 더하면 9개가 됩니다.

 

이 과정에서 규칙을 하나 찾을 수 있습니다.

우선 문제에서 입력으로 주어지는 수를 모두 더하면 양수라고 했습니다.

그리고 각 시작 지점을 i번이라고 했을 때 i번부터 N개의 누적합은 무조건 양수입니다.

 

제가 4개씩 끊은 구간들을 보시면 1번 구간의 수들에서 +1한 값들이 2번 구간이 되어 있습니다.

그리고 2번 구간에서 +1를 하면 3번 구간이 됩니다.

그 +1은 배열의 전체 누적합이 되고, 음수의 갯수는 음수 누적합 / 전체 누적합이 되는것을 알 수 있습니다.

계산하면 실수가 나오기 때문에 double형으로 바꿔주셔야 하고, 나머지는 무조건 올림 연산을 해야합니다.

이 방식으로 접근하시면 로직 자체는 간단하게 구현하실 수 있습니다.

이 문제는 이 방식을 생각해내는것 자체가 정말 어렵다는 것을 느꼈습니다.

 

 

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 <cmath>
#define MAX 20001
using namespace std;
typedef long long ll;
 
int dp[MAX];
int N;
 
void init() {
    for (int i = 1; i <= (N << 1); i++) {
        dp[i] += dp[i - 1];
    }
}
 
void func() {
    init();
 
    ll ret = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = i; j < N + i; j++) {
            if (dp[j] - dp[i - 1] >= 0) continue;
            ret += (ll)ceil((double)(-dp[j] + dp[i - 1]) / (double)(dp[N + i - 1] - dp[i - 1]));
        }
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
        dp[i + N] = dp[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

'algorithm > ad-hoc' 카테고리의 다른 글

boj 14370 전화번호 수수께끼 (Large)  (0) 2024.08.06
boj 21316 스피카  (0) 2024.08.05
boj 5527 전구 장식  (0) 2024.07.30
boj 14864 줄서기  (0) 2024.07.26
boj 2381 최대 거리  (0) 2024.07.25

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명 이상 모여야 지상에 강림한다고 합니다.

만약 신도들이 T명 미만으로 모였을 때 친구를 최대 K명까지 초대하여 T명을 맞출 수도 있습니다.

친구들은 친구들을 제외한 신도들이 T명 이상이 되었다면 모두 탈출한다고 하여 적절한 시기에만 친구를 불러야 합니다.

 

저는 dp로 문제에 접근했고, 우선 누적합을 통해 참여하는 신도들의 수를 시간별로 구합니다.

범위로 누적합을 구해야하기 때문에 imos 기법을 활용했습니다.

imos 기법으로 범위의 양 끝지점에만 카운팅을 먼저 하고, 마지막에 한번에 누적합을 구할 수 있습니다.

 

dp[N][K][pre]: N 시간에 친구 K명을 부를 수 있고, 이미 참여중인 친구가 pre명일 때 엘리스가 지상으로 강림하는 최대 시간

문제에서 나올 수 있는 경우는 4가지입니다.

1. 신도들만 T명 이상 모였을 경우

2. 신도 + 이미 참여중인 친구들이 T명 이상 모였을 경우

3. 친구들을 더 추가하여 T명을 채울 수 있는 경우

4. 친구들을 추가해도 T명을 채우지 못하는 경우

 

1번의 경우는 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

이미 참여중인 친구들이 있다면 모두 탈출하기 때문에 pre는 0으로 맞춥니다.

 

2번의 경우도 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

친구들을 제외한 시도들이 T보다 적으므로 pre도 그대로 유지합니다.

 

3번의 경우도 엘리스가 강림할 수 있으므로 +1을 하고 다음 시간을 확인합니다.

친구를 tmp명 더 추가합니다. pre는 pre + tmp가 되겠고, k에서도 tmp만큼 빼줍니다.

 

4번의 경우는 엘리스가 강림할 수 없으므로 바로 다음 시간을 확인합니다.

이때 친구들을 더 추가하지 않으며, 이미 참여중인 친구들은 계속 참여하기 때문에 pre를 그대로 유지합니다.

 

코드

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 <cstring>
#include <algorithm>
#define MAX 310
using namespace std;
 
int sum[MAX];
int dp[MAX][MAX][MAX];
int N, M, K, T;
 
int solve(int idx, int k, int pre) {
    if (idx > N) return 0;
    int& ret = dp[idx][k][pre];
    if (ret != -1) return ret;
 
    if (sum[idx] + pre >= T) {
        int next = pre;
        if (sum[idx] >= T) next = 0;
        return ret = solve(idx + 1, k, next) + 1;
    }
 
    ret = solve(idx + 1, k, pre);
    int tmp = T - sum[idx] - pre;
    if (k && k >= tmp) {
        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

'대회 > elice' 카테고리의 다른 글

엘리스 코드 챌린지 Day 10 계단 카드 뽑기  (0) 2024.07.24
엘리스 코드 챌린지 Day 9 격자 위의 ELICE  (0) 2024.07.24
엘리스 코드 챌린지 Day 7 계기판 조작하기  (0) 2024.07.23
엘리스 코드 챌린지 Day 6 빨간 선과 파란 선  (0) 2024.07.23
엘리스 코드 챌린지 Day 5 수열 복원  (0) 2024.07.22

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

+ Recent posts

티스토리툴바