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 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30

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 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
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30

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

 

25427번: DKSH를 찾아라

준혁이는 DKSH(단국대학교부속소프트웨어고등학교)에 다니는 학생이다. 어느 날, 준혁이는 길을 걷다가 $N$ 개의 알파벳 대문자가 써있는 종이를 발견했다. 평소에 자신이 DKSH에 다니는 학생이라

www.acmicpc.net

 

4개의 문자를 제외하고 모두 제거했을 때, 남은 문자열이 DKSH일 경우의 수를 구하는 문제입니다.

DKSH의 순서를 유지해야 하며, (a < b < c < d) 조건을 만족하는 (a, b, c, d) 쌍의 갯수를 구해야 합니다.

dp[idx][pos]: list의 idx번째 문자, DKSH 중 pos번쨰 문자를 확인할 때 "DKSH"를 만들 수 있는 경우의 수

 

우선 가장먼저 떠오른 방법이 재귀입니다.

pos == 4, 즉 DKSH를 모두 찾았다면 1을 리턴합니다.

DKSH를 모두 찾지 못했는데 list 내의 문자열을 모두 확인했다면 0을 리턴합니다.

모든 인덱스에 대해 해당 문자를 고르지 않고 idx + 1, pos번째 문자를 확인할 수 있습니다.

그리고 현재 idx번째 문자와 pos번째 문자가 일치하면 idx + 1, pos + 1번째 문자를 확인합니다.

두 가지의 경우를 모두 더해주시면 답이 되겠습니다.

 

여기까지 제가 생각했던 방법이고, 이 방법을 사용하지 않은 풀이도 존재합니다.

어떤 인덱스 idx를 기준으로 경우의 수를 조합하는 방법으로는

idx의 왼쪽에서 해당되는 문자의 갯수 * idx의 오른쪽에 해당되는 문자의 갯수로 구할 수 있습니다.

 

예시로 "YYYSSS"라는 문자열로 "YS"를 만들 수 있는 경우의 수는

왼쪽의 Y1 Y2 Y3 (3개) * 오른쪽의 S1 S2 S3 (3개) = 9로 구할 수 있습니다.

이를 변형해서 Y1 (S1 S2 S3) + Y2 (S1 S2 S3) + Y3 (S1 S2 S3)로도 구할 수 있으며, 이 문제는 이 방법을 이용합니다.

이 방법을 이용하여 해결할 수 있습니다.

찾은 문자에 대해서 왼쪽에 pos-1번 문자의 카운팅이 몇번 진행되었는지 확인만 해주면 됩니다.

'D'를 찾았다면 첫번째 문자이므로 d에 1을 더합니다.

'K'를 찾았다면 앞에 'D'가 카운팅 된 d를 k에 더해줍니다.

'S'를 찾았다면 앞에 'K'가 카운팅 된 k를 s에 더해줍니다.

'H'를 찾았다면 앞에 'S'가 카운팅 된 s를 h에 더해줍니다.

출력은 h를 해주시면 됩니다.

 

첫번째 방법
두번째 방법

역시 두번째 방법이 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
40
41
42
43
44
45
46
47
48
49
50
51
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX = 100000;
    private final static char pat[] = new char[]{'D', 'K', 'S', 'H'};
    private static char[] list;
    private static long dp[][] = new long[MAX][4];
    private static int N;
 
    private static long solve(int idx, int pos) {
        if (pos == 4) return 1;
        if (idx == N) return 0;
        if (dp[idx][pos] != -1) return dp[idx][pos];
        dp[idx][pos] = solve(idx + 1, pos);
 
        if (list[idx] == pat[pos]) {
            dp[idx][pos] += solve(idx + 1, pos + 1);
        }
 
        return dp[idx][pos];
    }
 
    private static void init() {
        for (int i = 0; i < N; i++) {
            Arrays.fill(dp[i], -1);
        }
    }
 
    private static void func() {
        init();
        System.out.println(solve(0, 0));
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        list = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static char[] list;
    private static int N;
 
    private static void func() {
        long d = 0;
        long k = 0;
        long s = 0;
        long h = 0;
        for (int i = 0; i < N; i++) {
            if (list[i] == 'D') d++;
            else if (list[i] == 'K') k += d;
            else if (list[i] == 'S') s += k;
            else if (list[i] == 'H') h += s;
        }
 
        System.out.println(h);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
 
        st = new StringTokenizer(br.readLine());
        list = st.nextToken().toCharArray();
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

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

boj 28018 시간이 겹칠까?  (0) 2023.08.08
boj 12841 정보대 등산  (0) 2023.07.31
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30

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

 

25682번: 체스판 다시 칠하기 2

첫째 줄에 정수 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.

www.acmicpc.net

2차원 배열 내 누적합 문제입니다.

2차원 누적합은 (sx, sy) ~ (ex, ey)의 누적합을 말하며, dp[i][j] = cur + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] 공식을 활용해야 합니다.

 

체스판은 검은색, 흰색이 번갈아 칠해져있어야 하고, (1, 1) 지점의 색은 정해지지 않았습니다.

따라서 (1, 1) 지점에 검은색이 올 경우와 흰색이 올 경우를 모두 구해서 최솟값을 구해야 합니다.

이를 위해 dp를 두개 사용합니다.

 

좌표의 x, y값을 더한 값이 홀수인 좌표들끼리와 짝수인 좌표들끼리의 색은 같습니다.

이를 활용하여 해당 좌표에 색이 바껴야하는지에 대해서 각각 누적합을 구할 수 있습니다.

dp를 채웠다면 K * K 크기의 정사각형의 누적합들을 순회하며 최솟값을 구하도록 합니다.

 

 

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
#include <iostream>
#include <algorithm>
#define MAX 2001
using namespace std;
 
char list[MAX][MAX];
int bdp[MAX][MAX], wdp[MAX][MAX];
int N, M, K;
 
void getPrefixSum() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            bdp[i][j] = bdp[i - 1][j] + bdp[i][j - 1] - bdp[i - 1][j - 1];
            wdp[i][j] = wdp[i - 1][j] + wdp[i][j - 1] - wdp[i - 1][j - 1];
 
            if (list[i][j] == 'W') {
                if ((i + j) % 2) {
                    wdp[i][j]++;
                }
                else {
                    bdp[i][j]++;
                }
            }
            else {
                if ((i + j) % 2) {
                    bdp[i][j]++;
                }
                else {
                    wdp[i][j]++;
                }
            }
        }
    }
}
 
void func() {
    getPrefixSum();
    int ret = 2147483647;
    for (int i = K; i <= N; i++) {
        for (int j = K; j <= M; j++) {
            ret = min(ret, bdp[i][j] - bdp[i - K][j] - bdp[i][j - K] + bdp[i - K][j - K]);
            ret = min(ret, wdp[i][j] - wdp[i - K][j] - wdp[i][j - K] + wdp[i - K][j - K]);
        }
    }
 
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 12841 정보대 등산  (0) 2023.07.31
boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30
boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30

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

 

12996번: Acka

첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S)

www.acmicpc.net

N곡을 세 사람이 나눠서 불러 앨범을 완성해야 합니다.

정확히 N곡을 불러야하며, 세 사람의 기회가 모두 소진되어야 합니다.

 

그러면 경우의 수를 얻는 조건은 N이 0이되면서 세 사람의 기회가 모두 0이 되는 경우에만 1을 추가합니다.

dp[N][x][y][z]: N곡이 남았고, 세 사람의 기회가 x, y, z만큼 있을 때 앨범을 완성할 수 있는 경우의 수

 

한 곡에 대해 부를 수 있는 경우는 아래와 같습니다.

  1. 세 사람 중 적어도 한 명 이상이 불러야 한다.
  2. 세 사람 모두가 한 곡을 불러도 된다.
  3. 세 사람 중 두 사람이 한 곡을 불러도 된다.
  4. 세 사람 중 한 사람이 한 곡을 불러도 된다.

이 문제는 간단하게 위의 경우를 하나씩 모두 구해주시면 되겠습니다.

경우의 수를 더하면서 % MOD 연산을 해주도록 합시다.

 

 

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
#include <iostream>
#include <cstring>
#define MAX 51
#define MOD 1000000007
using namespace std;
 
int dp[MAX][MAX][MAX][MAX];
int N, x, y, z;
 
int solve(int n, int a, int b, int c) {
    if (!n) {
        return !a && !b && !c;
    }
    
    int& ret = dp[n][a][b][c];
    if (ret != -1) return ret;
    ret = 0;
 
    if (a && b && c) {
        ret = (ret + solve(n - 1, a - 1, b - 1, c - 1)) % MOD;
    }
 
    if (a && b) {
        ret = (ret + solve(n - 1, a - 1, b - 1, c)) % MOD;
    }
    if (a && c) {
        ret = (ret + solve(n - 1, a - 1, b, c - 1)) % MOD;
    }
    if (b && c) {
        ret = (ret + solve(n - 1, a, b - 1, c - 1)) % MOD;
    }
 
    if (a) {
        ret = (ret + solve(n - 1, a - 1, b, c)) % MOD;
    }
    if (b) {
        ret = (ret + solve(n - 1, a, b - 1, c)) % MOD;
    }
    if (c) {
        ret = (ret + solve(n - 1, a, b, c - 1)) % MOD;
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(N, x, y, z) << '\n';
}
 
void input() {
    cin >> N >> x >> y >> z;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 25427 DKSH를 찾아라  (0) 2023.05.21
boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30
boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30
boj 2281 데스노트  (1) 2022.10.08

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

 

14450번: Hoof, Paper, Scissors (Gold)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s

www.acmicpc.net

가위바위보 마지막 문제입니다.

이 문제에서도 입력으로 상대방의 race가 주어지며, 베시는 같은 것만 여러번 연속으로 낼 수 있습니다.

Silver 문제와 다른 점은 K번까지 바꿀 수 있으며, K의 최대는 20입니다.

 

누적합으로는 해결할 수 없으며, dp와 재귀를 활용합니다.

dp[idx][cnt][race]: idx번째 게임에서 베시는 race를 cnt번 변경한 상태고, 현재 race를 낸 상태일 때 얻을 수 있는 최대 점수

3중 배열을 사용해야 하며, 첫 번째 게임에서 race를 낼 수 있는 경우 3가지를 모두 확인해야 합니다.

(race를 인덱스로 활용하고, 편의를 위해 입력에서 race를 숫자로 변경하였습니다.)

 

모든 경우에서 race를 변경하지 않고 연속으로 내는 경우를 구할 수 있고,

cnt < K인 경우에만 race를 변경하는 경우를 구하도록 합니다.

 

 

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    private final static int MAX_N = 100001;
    private final static int MAX_K = 21;
    private static final int RACE_CNT = 3;
    private static int list[] = new int[MAX_N];
    private static int dp[][][] = new int[MAX_N][MAX_K][RACE_CNT];
    private static int N, K;
 
    private static void init() {
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
    }
 
    private static int getScore(int x, int y) {
        if (x == 0 && y == 1) {
            return 1;
        } else if (x == 1 && y == 2) {
            return 1;
        } else if (x == 2 && y == 0) {
            return 1;
        } else {
            return 0;
        }
    }
 
    private static int dfs(int idx, int cnt, int race) {
        if (idx > N) {
            return 0;
        }
        if (dp[idx][cnt][race] != -1) {
            return dp[idx][cnt][race];
        }
 
        dp[idx][cnt][race] = dfs(idx + 1, cnt, race) + getScore(race, list[idx]);
        if (cnt < K) {
            dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 1) % RACE_CNT) + getScore(race, list[idx]));
            dp[idx][cnt][race] = Math.max(dp[idx][cnt][race], dfs(idx + 1, cnt + 1, (race + 2) % RACE_CNT) + getScore(race, list[idx]));
        }
 
        return dp[idx][cnt][race];
    }
 
    private static void func() {
        init();
        System.out.println(Math.max(dfs(1, 0, 0), Math.max(dfs(1, 0, 1), dfs(1, 0, 2))));
    }
 
    private static int getRace(char x) {
        if (x == 'H') {
            return 0;
        } else if (x == 'S') {
            return 1;
        } else {
            return 2;
        }
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = getRace(st.nextToken().charAt(0));
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

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

boj 25682 체스판 다시 칠하기 2  (0) 2023.02.26
boj 12996 Acka  (0) 2023.01.29
boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30
boj 2281 데스노트  (1) 2022.10.08
boj 2015 수들의 합 4  (0) 2022.08.12

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

 

14453번: Hoof, Paper, Scissors (Silver)

You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game they call "Hoof, Paper, Scissors". The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count to three and then each s

www.acmicpc.net

입력으로 상대방의 race를 확인할 수 있으며, 그거에 맞도록 적절한 race를 결정해야 합니다.

그리고 베시는 같은 것만 여러번 연속으로 낼 수 있으며, 최대 한 번만 바꿀 수 있습니다.

 

이 문제는 누적합을 활용할 수 있습니다.

입력으로 주어지는 race의 P, H, S의 누적 합을 각각 구하고,

베시가 race를 변경할 어떤 구간을 기준으로 왼쪽, 오른쪽의 P, H, S의 누적합의 최대를 더한 값으로 구할 수 있습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static class Point{
        int pCnt;
        int hCnt;
        int sCnt;
 
        public Point(int p, int h, int s) {
            pCnt = p;
            hCnt = h;
            sCnt = s;
        }
    }
 
    private static final int MAX = 100001;
    private static Point[] dp = new Point[MAX];
    private static int N;
 
    private static void func() {
        int ret = Math.max(dp[N].pCnt, Math.max(dp[N].hCnt, dp[N].sCnt));
        for(int i = 1; i < N; i++) {
            int l = Math.max(dp[i].pCnt, Math.max(dp[i].hCnt, dp[i].sCnt));
            int r = Math.max(dp[N].pCnt - dp[i].pCnt, Math.max(dp[N].hCnt - dp[i].hCnt, dp[N].sCnt - dp[i].sCnt));
 
            ret = Math.max(ret, l + r);
        }
 
        System.out.println(ret);
    }
 
    private static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        char x;
        N = Integer.parseInt(st.nextToken());
        dp[0] = new Point(0, 0, 0);
        for (int i = 1; i <= N; i++) {
            dp[i] = new Point(0, 0, 0);
            st = new StringTokenizer(br.readLine());
            x = st.nextToken().charAt(0);
 
            if (x == 'P') {
                dp[i].pCnt++;
            } else if (x == 'H') {
                dp[i].hCnt++;
            } else {
                dp[i].sCnt++;
            }
 
            dp[i].pCnt += dp[i - 1].pCnt;
            dp[i].hCnt += dp[i - 1].hCnt;
            dp[i].sCnt += dp[i - 1].sCnt;
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 
 cs

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

boj 12996 Acka  (0) 2023.01.29
boj 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30
boj 2281 데스노트  (1) 2022.10.08
boj 2015 수들의 합 4  (0) 2022.08.12
boj 21923 곡예 비행  (0) 2022.06.10

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

 

2281번: 데스노트

첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m

www.acmicpc.net

노트에 이름을 순서대로 적기 위한 조건은 아래와 같습니다.

  1. 위에서 아래로 적습니다.
  2. 같은 줄에서는 왼쪽에서 오른쪽으로 적습니다.
  3. 이름 사이에는 한 칸의 빈 칸이 있습니다.
  4. 한 사람의 이름은 한 줄에만 적어야 하며, 해당 줄에 사람의 이름을 다 적지 못하면 다음 줄에 적어야 합니다.
  5. 한 줄을 넘어가는 길이의 이름은 주어지지 않습니다.

위 조건을 지키면서 이름을 적으며, 마지막 줄을 제외한 모든 줄에서 끝에 남은 칸의 갯수의 제곱을 더한 값의 최소를 구하는 문제입니다.

 

dp[idx][len]: idx번째 이름을 적을 차례이고, idx - 1번째까지 len의 공간을 사용했을 때의 최솟값

여기서 선택할 수 있는 방법은

  1. 현재 줄을 빈 칸으로 놔두고 다음 줄에 이름을 적는다.
  2. 현재 줄에 남은 칸이 이름의 길이만큼 남았다면 현재 줄에 이름을 적는다.

이렇게 두 가지 있습니다.

1번은 모든 경우에 할 수 있으며, 2번은 남은 공간을 파악하여 구하도록 합니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1001
using namespace std;
 
int dp[MAX][MAX], list[MAX];
int N, M;
 
int solve(int idx, int len) {
    if (idx == N) return 0;
 
    int& ret = dp[idx][len];
    if (ret != -1) return ret;
    
    ret = (M - len + 1) * (M - len + 1) + solve(idx + 1, list[idx] + 1);
    if (len + list[idx] <= M) {
        ret = min(ret, solve(idx + 1, len + list[idx] + 1));
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0) << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; 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 14450 Hoof, Paper, Scissors (Gold)  (0) 2022.12.30
boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30
boj 2015 수들의 합 4  (0) 2022.08.12
boj 21923 곡예 비행  (0) 2022.06.10
boj 12978 스크루지 민호 2  (0) 2022.06.08

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

 

2015번: 수들의 합 4

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로

www.acmicpc.net

N이 20만이므로 모든 부분합을 직접 구할 수는 없습니다.

기존의 누적합 문제에서 부분합을 구하는 식은 dp[r] - dp[l - 1] = K 입니다.

K는 입력으로 주어지기 때문에 식을 변형하면 dp[r] - K = dp[l - 1]이 되고, 이 식으로 문제에 접근합니다.

 

식을 풀어서 설명하면 dp[r](1 ~ r번 요소의 누적합) - K = dp[l - 1](1 ~ l - 1번 요소의 누적합)

이렇게 되는데, l - 1번을 구할 필요는 없습니다. dp[r] - K와 일치하는 값이 몇 번 나왔는지 세어주면 되는겁니다.

이를 계산하기 위해 map을 사용합니다. 정렬이 필요없으므로 unordred_map을 사용하였습니다.

 

누적합을 구하면서 dp[i] - K 값이 map에 있다면 map[dp[i] - K]만큼 카운트를 증가시킵니다.

그리고 dp[i] 값을 새롭게 map에 넣어주거나 1을 증가시킵니다.

dp[i] 값이 K인 경우는 ans를 따로 증가시켜야 합니다.

 

N = 200000, K = 0이고, 배열의 값이 모두 0이라면 int 범위를 넘으므로 long long을 사용해야 합니다.

 

 

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
#include <iostream>
#include <unordered_map>
#define MAX 200001
using namespace std;
typedef long long ll;
 
int dp[MAX];
int N, K;
 
void func() {
    unordered_map<int, ll> m;
    ll ans = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] += dp[i - 1];
        if (dp[i] == K) ans++;
 
        if (m.find(dp[i] - K) != m.end()) {
            ans += m[dp[i] - K];
        }
 
        if (m.find(dp[i]) != m.end()) {
            m[dp[i]]++;
        }
        else {
           m.insert({ dp[i], 1LL });
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

 

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

boj 14453 Hoof, Paper, Scissors (Silver)  (0) 2022.12.30
boj 2281 데스노트  (1) 2022.10.08
boj 21923 곡예 비행  (0) 2022.06.10
boj 12978 스크루지 민호 2  (0) 2022.06.08
boj 10986 나머지 합  (0) 2022.03.08

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

 

21923번: 곡예 비행

동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행

www.acmicpc.net

상승 비행을 할 때 지나간 칸에 부여된 점수의 합 + 하강 비행을 할 때 지나간 칸에 부여된 점수의 합을 구합니다.

이 문제의 예제 입력 5번을 보시면 상승 비행과 하강 비행 시 좌표가 겹칠 수 있다는 것을 알 수 있습니다.

따라서 비행이 끝났다는 것은 "좌표가 맨 우측 아래이고, 하강 비행 중일 때"가 됩니다.

 

모든 좌표들을 대상으로 상승, 하강 비행을 해야하며, 기본적인 dfs에 중복 방문 체크를 위해 dp를 사용합니다.

dp[x][y][flag] : 좌표 (x, y)에 flag 상태로 도달했을 때 얻을 수 있는 최대 비행 점수

여기서 flag란 상승 비행인지, 하강 비행인지를 나타내며,

flag = 0이면 상승 비행, flag = 1이면 하강 비행입니다.

그리고 모든 좌표에 대해 상승, 하강 비행을 해야하므로 3차원 배열 dp를 사용합니다.

 

이 문제에서 입력은 음수도 주어지므로 dp를 최솟값으로 초기화해줍니다.

그리고 좌측 아래 좌표 (N - 1, 0)을 시작점으로 dfs 순회합니다.

현재 상승 비행 중이라면 현재 좌표에서 하강 비행으로 변경 후 최대 점수를 먼저 구해줍니다.

그 다음 현재 좌표에 대해 상승 / 하강 비행을 구분하여 다음 좌표로 진행해줍니다.

비행이 끝났을 때는 (N - 1, M - 1)에 하강 비행 중인 상태에 도달했을 때가 되겠고, 해당 좌표값인 list[x][y]를 리턴합니다.

다른 경우에는 ret의 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
#include <cstring>
#define MAX 1001
using namespace std;
 
int list[MAX][MAX], dp[MAX][MAX][2];
int direct[2][2][2] = { 
    {{0,1},{-1,0}},
    {{0,1},{1,0}}
};
int N, M;
 
int dfs(int x, int y, int flag) {
    if (x == N - 1 && y == M - 1 && flag) {
        return list[x][y];
    }
 
    int& ret = dp[x][y][flag];
    if (ret != -1e9) return ret;
 
    if (!flag) ret = dfs(x, y, !flag);
    for (int d = 0; d < 2; d++) {
        int nx = x + direct[flag][d][0];
        int ny = y + direct[flag][d][1];
 
        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
 
        ret = max(ret, dfs(nx, ny, flag));
    }
 
    ret += list[x][y];
    return ret;
}
 
void func() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = -1e9;
            }
        }
    }
 
    cout << dfs(N - 1, 0, 0) << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 2281 데스노트  (1) 2022.10.08
boj 2015 수들의 합 4  (0) 2022.08.12
boj 12978 스크루지 민호 2  (0) 2022.06.08
boj 10986 나머지 합  (0) 2022.03.08
boj 14238 출근 기록  (0) 2022.02.04

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

 

12978번: 스크루지 민호 2

구두쇠로 유명한 스크루지 민호가 다스리는 천나라가 있다. 천나라에는 N 개의 도시들이 있는데 각각의 도시들 사이에는 양방향 도로로 이어져 있다. 민호는 도시를 세울 때 최소한의 비용만을

www.acmicpc.net

오랜만에 알고리즘 포스팅입니다.

 

N개의 도시와 N - 1개의 도로인 것으로 보아 트리 문제인 것으로 파악할 수 있으며,

최소 갯수의 경찰서를 세워 모든 도시, 도로를 감시해야 합니다.

 

모든 도시들 대상으로 경찰서를 세우는 경우, 세우지 않는 경우를 모두 구한다면 시간초과가 발생할 것입니다.

따라서 dp를 추가하여 treedp로 접근합니다.

 

dp[v][flag]: 현재 도시가 v이고, 상태가 flag일 때 세워야할 경찰서의 최소 갯수

여기서 상태란, 현재 도시에 경찰서를 세울지 결정하는 변수입니다.

flag = 1 일 때, 해당 도시에 경찰서를 세우고,

flag = 0 일 때, 해당 도시에 경찰서를 세우지 않는 경우입니다.

 

이러면 다음 도시부터는 계산하기 수월해집니다.

현재 도시에서 경찰서를 세웠더라면 다음 도시에서는 경찰서를 세워도 되고, 세우지 않아도 됩니다. 즉, 두 경우 모두 확인합니다.

현재 도시에서 경찰서를 세우지 않았더라면 다음 도시에서는 경찰서를 무조건 세워야 합니다. 즉, 하나의 경우만 확인합니다.

마지막으로 해당 경우의 합의 최솟값을 출력합니다.

 

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define MAX 100001
using namespace std;
 
vector<int> graph[MAX];
int dp[MAX][2];
int N;
 
int dfs(int v, int pre, int flag) {
    int& ret = dp[v][flag];
    if (ret != -1) return ret;
    ret = flag;
 
    for (auto next : graph[v]) {
        if (pre == next) continue;
        if (flag) {
            ret += min(dfs(next, v, 1), dfs(next, v, 0));
        }
        else {
            ret += dfs(next, v, 1);
        }
    }
 
    return ret;
}
 
void func() {
    memset(dp, -1, sizeof(dp));
    cout << min(dfs(1, 0, 1), dfs(1, 0, 0)) << '\n';
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 2015 수들의 합 4  (0) 2022.08.12
boj 21923 곡예 비행  (0) 2022.06.10
boj 10986 나머지 합  (0) 2022.03.08
boj 14238 출근 기록  (0) 2022.02.04
boj 3673 나눌 수 있는 부분 수열  (0) 2022.01.31

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

 

10986번: 나머지 합

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j)

www.acmicpc.net

[boj 3673 나눌 수 있는 부분 수열] 문제와 같은 풀이 방법입니다.

 

모든 수열의 누적합을 구해 각각의 누적 합의 %M 값을 사용합니다.

1
2
5 3
1 2 3 1 2
 cs

위의 입력을 예시로 들면

1
2
sum   = 1 3 6 7 9
MOD M = 1 0 0 1 0
 cs

이렇게 됩니다. 저는 이번 문제는 dp에 MOD M한 값을 미리 저장해두었고, cnt[dp[i]]으로 카운팅 하였습니다.

 

M = 3이므로

나머지가 0인 갯수는 3

나머지가 1인 갯수는 2이므로

 

나머지가 같은 부분 수열에서 2개를 뽑는 조합을 더하는 식으로 구할 수 있습니다.

 

 

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
#include <iostream>
#define MAX_N 1000001
#define MAX_M 1001
using namespace std;
typedef long long ll;
 
ll cnt[MAX_M], ans;
int dp[MAX_N];
int N, M;
 
void func() {
    ans = cnt[0];
    for (int i = 0; i < M; i++) {
        ans += (cnt[i] * (cnt[i] - 1) / 2LL);
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
 
        dp[i] = (dp[i] + dp[i - 1]) % M;
        cnt[dp[i]]++;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 21923 곡예 비행  (0) 2022.06.10
boj 12978 스크루지 민호 2  (0) 2022.06.08
boj 14238 출근 기록  (0) 2022.02.04
boj 3673 나눌 수 있는 부분 수열  (0) 2022.01.31
boj 20500 Ezreal 여눈부터 가네 ㅈㅈ  (0) 2022.01.01

+ Recent posts

티스토리툴바