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

 

3673번: 나눌 수 있는 부분 수열

양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누

www.acmicpc.net

M으로 나누어 떨어지는 연속하는 부분 수열의 합의 갯수를 찾는 문제입니다.

이 문제의 키워드는 "연속" 이며, 누적 합을 이용합니다.

 

1
2
M = 4, N = 8
2 1 2 1 1 2 1 2
 cs

위의 입력을 예시로 우선 수열의 누적합을 구해 각각의 MOD M을 구합니다.

 

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

그러면 위와 같이 누적 합과 누적 합의 MOD M 값을 카운팅합니다.

 

M = 4이므로

나머지가 0인 갯수는 1

나머지가 1인 갯수는 2

나머지가 2인 갯수는 3

나머지가 3인 갯수는 2

이렇게 됩니다.

 

여기서 나머지가 1인 부분 수열을 설명하면

sum(1 ~ 3), sum(1 ~ 6)의 나머지가 1로 같다는 말입니다.

그러면 sum(4 ~ 6)의 나머지는 0이라는 말이 됩니다.

따라서 나머지가 같은 부분 수열에서 2개를 뽑는 조합을 구하면 되는 겁니다.

 

나머지가 1인 부분 수열은 2개이므로 2개 중에 2개를 뽑는 경우의 수: 1

 

나머지가 2인 부분 수열은

sum(1 ~ 1), sum(1 ~ 4), sum(1 ~ 7)로 3개로

3개 중에 2개를 뽑는 경우의 수로 3이라는 답이 나옵니다.

 

같은 방식으로 나머지가 0 ~ M - 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
#include <iostream>
#include <cstring>
#define MAX_N 50001
#define MAX_M 1000000
using namespace std;
typedef long long ll;
 
ll dp[MAX_N], cnt[MAX_M];
int N, M;
 
void func() {
    ll ans = cnt[0];
    for (int i = 0; i < M; i++) {
        if (cnt[i] < 2) continue;
        ans += ((cnt[i] * (cnt[i] - 1)) / 2LL);
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> M >> N;
    for (int i = 1; i <= N; i++) {
        cin >> dp[i];
        dp[i] += dp[i - 1];
 
        cnt[dp[i] % M]++;
    }
}
 
void init() {
    memset(cnt, 0, sizeof(cnt));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
        init();
    }
 
    return 0;
}
 cs

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

boj 10986 나머지 합  (0) 2022.03.08
boj 14238 출근 기록  (0) 2022.02.04
boj 20500 Ezreal 여눈부터 가네 ㅈㅈ  (0) 2022.01.01
boj 1135 뉴스 전하기  (0) 2021.11.15
boj 17090 미로 탈출하기  (0) 2021.06.27

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

 

20500번: Ezreal 여눈부터 가네 ㅈㅈ

문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

www.acmicpc.net

1과 5로만 이루어진 N자리 양의 정수 중에서 15의 배수가 몇 개인지 구하는 문제입니다.

 

15의 배수는 3의 배수 * 5의 배수입니다.

따라서 3의 배수이고, 5의 배수인 것을 찾으면 됩니다.

 

dp[N][R]: N자리의 양의 정수를 3으로 나눈 나머지가 R인 경우의 수

따라서 먼저 5의 배수를 만들어 놓고, 3으로 나눈 나머지를 확인하도록 합니다.

 

우선 N = 1일때는 15의 배수가 없으므로 패스합니다.

N = 2일때는 5의 배수가 15, 55가 있습니다.

15는 3으로 나눈 나머지가 0이므로 dp[2][0]에 해당하고,

55는 3으로 나눈 나머지가 1이므로 dp[2][1]에 해당합니다.

따라서 초기 값은 dp[2][0] = 1, dp[2][1] = 1입니다.

 

그 다음 N = 3일때는 N = 2일 경우에 1 또는 5를 붙인 경우를 더해주시면 됩니다.

dp[3][0]은 dp[2][1]에서 앞자리에 5를 더한 경우 + dp[2][2]에서 앞자리에 1을 더한 경우

dp[3][1]은 dp[2][0]에서 앞자리에 1을 더한 경우 + dp[2][2]에서 앞자리에 5를 더한 경우

dp[3][2]는 dp[2][0]에서 앞자리에 5를 더한 경우 + dp[2][1]에서 앞자리에 1을 더한 경우

 

따라서 점화식은 위와같이

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

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

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

이렇게 됩니다.

 

결과로는 MOD를 한 값을 출력해야 하므로 더하면서 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
#include <iostream>
#define MAX 1516
#define MOD 1000000007
using namespace std;
 
int dp[MAX][3];
int N;
 
void init() {
    dp[2][0] = 1;
    dp[2][1] = 1;
    for (int i = 3; i < MAX; i++) {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % MOD;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % MOD;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
    }
}
 
void input() {
    cin >> N;
    cout << dp[N][0] << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
 
    return 0;
}
 cs

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

boj 14238 출근 기록  (0) 2022.02.04
boj 3673 나눌 수 있는 부분 수열  (0) 2022.01.31
boj 1135 뉴스 전하기  (0) 2021.11.15
boj 17090 미로 탈출하기  (0) 2021.06.27
boj 1648 격자판 채우기  (0) 2021.06.22

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

 

1135번: 뉴스 전하기

민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다

www.acmicpc.net

 

TreeDP는 난이도도 생각보다 높고, 많이 못 풀어봤어서 그런지 어렵네요..

 

0번 직원부터 시작해서 모든 직원에게 뉴스를 전하는데 최소 시간을 구하는 문제입니다.

한 번에 한 명에게만 전파가 가능하므로 전파하는 시간이 가장 오래걸리는 직속 부하에게 먼저 전파를 해야합니다.

 

list라는 벡터에 자신의 직속 부하에게 전파하는 시간을 모두 저장한 후에 내림차순으로 정렬합니다.

먼저 전파하는 부하에게는 추가적인 시간이 필요하지 않으므로 +0,

두 번째 전파하는 부하에게는 추가적인 시간이 +1,

마지막에 전파하는 부하에게는 list.size() - 1 만큼 추가적인 시간이 추가됩니다.

이 경우들의 최댓값이 자신의 부하직원에게 소식을 전하는데 걸리는 최소 시간입니다.

 

24번째 줄 +1을 한 이유는 부하가 없는 직원에게서 오는 값은 0이기 때문에 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
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 50
using namespace std;
 
vector<int> graph[MAX];
int N;
 
int dfs(int v) {
    vector<int> list;
    int ret = 0;
 
    for (int i = 0; i < graph[v].size(); i++) {
        int next = graph[v][i];
 
        list.push_back(dfs(next));
    }
    sort(list.begin(), list.end(), [](int a, int b) {
        return a > b;
    });
 
    for (int i = 0; i < list.size(); i++) {
        ret = max(ret, list[i] + i + 1);
    }
 
    return ret;
}
 
void func() {
    cout << dfs(0) << '\n';
}
 
void input() {
    int x;
    cin >> N >> x;
    for (int i = 1; i < N; i++) {
        cin >> x;
        graph[x].push_back(i);
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 3673 나눌 수 있는 부분 수열  (0) 2022.01.31
boj 20500 Ezreal 여눈부터 가네 ㅈㅈ  (0) 2022.01.01
boj 17090 미로 탈출하기  (0) 2021.06.27
boj 1648 격자판 채우기  (0) 2021.06.22
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22

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

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문

www.acmicpc.net

 

https://emoney96.tistory.com/24

 

boj 1103 게임

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여

emoney96.tistory.com

dfs + dp 문제이며 위의 문제와 비슷한 방법으로 해결하였습니다.

 

대신 게임 문제는 방향이 정해져있지 않아서 4방향 모두 확인해야하지만 이 문제는 1방향만 확인하면 되는 문제입니다.

현재 좌표의 방향으로 이동하면서 맵 밖으로 나가면 1을 리턴, visit으로 사이클을 체크해서 사이클이 발생했으면 0을 리턴합니다.

 

N * M번 모두 돌려가면서 ans를 구하였습니다.

 

 

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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static char list[][] = new char[510][510];
    static boolean visit[][] = new boolean[510][510];
    static int dp[][] = new int[510][510];
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, ans;
 
    static int dfs(int x, int y) {
        if (visit[x][y])
            return 0;
        visit[x][y] = true;
 
        if (dp[x][y] != -1)
            return dp[x][y];
 
        int d = 0;
        if (list[x][y] == 'D')
            d = 1;
        else if (list[x][y] == 'R')
            d = 0;
        else if (list[x][y] == 'U')
            d = 3;
        else
            d = 2;
 
        int nx = x + direct[d][0];
        int ny = y + direct[d][1];
 
        if (nx < 0 || nx >= N || ny < 0 || ny >= M)
            dp[x][y] = 1;
        else {
            dp[x][y] = dfs(x + direct[d][0], y + direct[d][1]);
            visit[nx][ny] = false;    
        }
 
        return dp[x][y];
    }
 
    static void func() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (dp[i][j] != -1) {
                    ans += dp[i][j];
                    continue;
                }
                ans += dfs(i, j);
                visit[i][j] = false;
            }
        }
 
        System.out.println(ans);
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            list[i] = st.nextToken().toCharArray();
            Arrays.fill(dp[i], -1);
        }
 
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
    }
}
 cs

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

boj 20500 Ezreal 여눈부터 가네 ㅈㅈ  (0) 2022.01.01
boj 1135 뉴스 전하기  (0) 2021.11.15
boj 1648 격자판 채우기  (0) 2021.06.22
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21

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

 

1648번: 격자판 채우기

준규는 침대에 누워서 천장을 바라보고 있었다. 천장은 격자판 모양이었고, 계속해서 천장을 바라보다 보니 이런 생각이 들었다. 세로 크기가 N이고, 가로 크기가 M인 격자판을 2x1 크기의 도미노

www.acmicpc.net

dp + 비트마스킹 문제로 넴모넴모(문제 링크) 문제와 비슷한 방식으로 해결하였습니다.

(안 푸셨으면 풀어 보시는거 추천드립니다 ㅎㅎ)

 

dp[x][bit] : x번 칸부터 M개의 칸의 상태가 bit일 때 x번 칸에 도미노를 놓는 경우의 수

이렇게 두고 해결하였습니다.

 

넴모넴모 문제는 x번 칸 이전의 M + 1개의 칸을 비트로, 이 문제는 x번 칸부터 M개의 칸을 비트로 두었습니다.

그리고 넴모넴모 문제는 x번 칸 뒤에는 채워져있지 않지만 이 문제는 채워져있을 가능성이 있어 확인을 해야하고,

0번 ~ x - 1번 칸은 모두 채워져있도록 로직을 구성하였습니다.

만약 2 * 3 격자판에 칸이 이렇게 채워져있고, x번 칸 차례라고 한다면,

x번 부터 x + (M - 1)번까지 M개의 비트는 역순으로 011로 구성됩니다.

 

우선 위 그림처럼 x번 칸이 이미 채워져있으면 다음 칸(x + 1)으로 넘어갑니다.

 

이렇게 x번 칸이 비워져있을 경우에만 1 * 2 크기나, 2 * 1 크기로 채울 수 있습니다.

위 그럼은 x + 1번 칸이 이미 채워져있으므로 1 * 2 크기는 채울 수 없습니다.

x + M번은 무조건 비어있으므로 2 * 1 크기로 채운 후 다음(x + 1)으로 넘어갈 수 있습니다.

 

이 그림은 x + 1번 칸이 비어있으므로 1 * 2크기를 채운 후 다음(x + 2)으로 넘어갈 수 있습니다.

x + M번은 무조건 비어있으므로 2 * 1 크기로 채운 후 다음(x + 1)으로 넘어갈 수 있습니다.

 

다만 이 그림처럼 맨 밑 칸은 2 * 1을 놓을 수 없으므로 맨 밑 칸이 아닐 경우에만 채워줍니다.

마지막으로 x번이 맨 오른쪽 칸일 경우에는 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
#include <iostream>
#include <cstring>
#define MAX 14
#define MOD 9901
using namespace std;
 
int dp[MAX * MAX][1 << MAX];
int N, M;
 
int func(int x, int bit) {
    if (x == N * M) return 1;
 
    int &ret = dp[x][bit];
    if (ret != -1) return ret;
    ret = 0;
 
    if (bit & 1) ret = func(x + 1, (bit >> 1));
    else {
        if (x / M != N - 1) ret = func(x + 1, (bit >> 1) | (1 << (M - 1)));
 
        if (x%M != M - 1 && !(bit & 2)) ret = (ret + func(x + 2, bit >> 2)) % MOD;
    }
 
    return ret;
}
 
void input() {
    cin >> N >> M;
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

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

boj 1135 뉴스 전하기  (0) 2021.11.15
boj 17090 미로 탈출하기  (0) 2021.06.27
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 1577 도로의 개수  (0) 2021.06.20

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

 

14700번: 넴모넴모 (Hard)

첫 번째 줄에 주어진 격자판에서 나올 수 있는, “넴모”들이 올라간 칸이 2 × 2 사각형을 이루지 않는 모든 배치의 가짓수를 1, 000, 000, 007로 나눈 나머지를 출력한다.

www.acmicpc.net

dp + 비트마스킹 문제로 격자판 채우기(문제 링크) 문제와 비슷한 방식으로 해결하였습니다. 

(안 푸셨으면 풀어 보시는거 추천드립니다 ㅎㅎ)

 

dp[x][chk] : x번 칸에서 이전 M + 1개의 칸에 넴모가 채워져있는 상태가 chk인 경우의 수

이렇게 두고 해결하였습니다.

 

격자판 채우기 문제는 x번 칸부터 M개의 칸을 비트로 다루었고, 이 문제는 x번 칸 이전의 M+1개의 칸을 비트로 다루었습니다.

 

우선 맨 왼쪽 칸은 무조건 넴모를 놓을 수 있습니다.. 그 칸에 놓음으로 2 * 2 사각형을 만들 수 없기 때문입니다.

이부분도 생각해주셔야합니다. (x % M == 0 인 곳)

만약 2 * 3 격자판에 칸이 이렇게 채워져있고, x번 칸 차례라고 한다면,

M + 1개의 비트는 x - 1부터 해서 역순으로 1101이라고 생각하시면 됩니다.

그럼 x번 칸에서 봐야할 비트는 (1 << 0) , (1 << 1), (1 << M) 이렇게 3개입니다.

위의 그림에서는 (1 << 1) 비트가 0이므로 x에는 넴모를 올려놓은 것, 올려놓지 않은 것 모두 확인할 수 있습니다.

만약 이 그림이라면 3개의 비트 모두 1이므로 x에는 넴모를 올려놓지 않은 것만 확인하시면 됩니다.

 

 

그리고.. 이 문제가 메모리가 빠듯해서 그런지 1 << 19로 잡아도 메모리 초과가 발생하였습니다.

입력이 N * M <= 300으로 들어오기때문에 10 * 30 이런것도 들어올 수 있다는 것인데

비트는 M + 1개를 다루기 때문에 메모리 공간을 잡는데 어려움이 있었습니다.

17 * 17 = 289이고 18 * 18 = 324이므로 아무리 커도 N과 M 중 작은쪽은 17보다 클 수 없다는 생각을 하였고,

둘 중 작은쪽을 M으로 가게 하였습니다.

 

시간 제한이 2초인데 1.6초로 겨우 AC를 받았습니다..

 

 

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>
#include <cstring>
#define MOD 1000000007
using namespace std;
 
int dp[301][1 << 18];
int N, M;
 
int func(int x, int chk) {
    if (x == N * M) return 1;
 
    int &ret = dp[x][chk];
    if (ret != -1) return ret;
    ret = 0;
 
    ret = func(x + 1, chk >> 1);
 
    if (!(x % M) || !(chk & (1 << 0)) || !(chk & (1 << 1)) || !(chk & (1 << M))) {
        ret = (ret + func(x + 1, (chk >> 1) | (1 << M))) % MOD;
    }
 
    return ret;
}
 
void input() {
    cin >> N >> M;
    if (N < M) swap(N, M);
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

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

boj 17090 미로 탈출하기  (0) 2021.06.27
boj 1648 격자판 채우기  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19

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

 

1311번: 할 일 정하기 1

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매

www.acmicpc.net

외판원 문제를 풀때는 dp + 비트마스킹에 적응을 못했어서 푸는데 어려움이 많았지만 이번 문제는 좀 수월하게 했던것 같습니다..

 

dp[x][cost] : x번 사람이 고를 때 x - 1번째 사람까지 골랐던 일의 상태가 cost인 비용의 최솟값

여기서 cost에 비트마스킹을 이용합니다. (N = 20이므로 약 100만 정도의 크기입니다.)

 

저는 번호를 0 ~ N - 1로 두었기때문에 0번 사람부터 차례로 0 ~ N - 1번 일까지 돌면서 고르지 않은 일만 선택하였고,

x가 N일 때 모든 사람이 일을 골랐으면 0, 아니면 INF을 리턴하였습니다.

 

 

+ 음.. 시간과 메모리가 적게 나온 분의 풀이를 보았는데 dp[x][cost]가 아닌 dp[cost]만으로도 해결이 됐습니다..

dp[cost] : 고른 일의 상태가 cost일 때 비용의 최솟값

으로 두고 해결하면 될 것 같습니다! (소스는 같이 올리겠습니다)

 

역시 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
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 20
#define INF 1000000000
using namespace std;
 
int list[MAX][MAX], dp[MAX][1 << MAX];
int N, chk;
 
int func(int x, int cost) {
    if (x == N) {
        if(cost == chk) return 0;
        else return INF;
    }
 
    int &ret = dp[x][cost];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < N; i++) {
        if (cost & (1 << i)) continue;
 
        ret = min(ret, func(x + 1, cost | (1 << i)) + list[x][i]);
    }
 
    return ret;
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    chk = (1 << N) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

 

 

[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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 20
#define INF 1000000000
using namespace std;
 
int list[MAX][MAX], dp[1 << MAX];
int N, chk;
 
int func(int x, int cost) {
    if (x == N) {
        if(cost == chk) return 0;
        else return INF;
    }
 
    int &ret = dp[cost];
    if (ret != -1) return ret;
    ret = INF;
 
    for (int i = 0; i < N; i++) {
        if (cost & (1 << i)) continue;
 
        ret = min(ret, func(x + 1, cost | (1 << i)) + list[x][i]);
    }
 
    return ret;
}
 
void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> list[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    chk = (1 << N) - 1;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
 
    return 0;
}
 cs

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

boj 1648 격자판 채우기  (0) 2021.06.22
boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19

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

 

1577번: 도로의 개수

첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 100보다 작거나 같은

www.acmicpc.net

(0, 0)에서 출발하여 (N, M)에 도착할 수 있는 경우의 수를 구하는문제입니다.

다만 이 문제는 공사중이어서 갈 수 없는 길이 존재하는데 거리는 항상 1이므로 set으로 관리하였습니다.

 

(a, b), (c, d) 형식으로 입력이 주어지면 (a, b)에서 (c, d)로 가는 길, (c, d)에서 (a, b)로 가는 길 모두 체크하였습니다.

로직은 dfs+dp으로 구성하였고, 이동은 최단거리로만 이동하기 때문에 뒤로는 가지 않아야합니다.

 

이 문제의 답은 long long 범위라고 명시되어 있으므로 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
48
49
50
51
52
#include <iostream>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
 
set<pair<int, int> > s[101][101];
ll dp[101][101];
int list[101][101];
int direct[2][2] = { {0,1},{1,0} };
int N, M, K;
 
ll func(int x, int y) {
    if (x == N && y == M) return 1;
 
    ll &ret = dp[x][y];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 2; i++) {
        int nx = x + direct[i][0];
        int ny = y + direct[i][1];
 
        if (nx > N || ny > M) continue;
        if (s[x][y].find({ nx,ny }) != s[x][y].end()) continue;
 
        ret += func(nx, ny);
    }
 
    return ret;
}
 
void input() {
    int sx, sy, ex, ey;
    cin >> N >> M >> K;
    while (K--) {
        cin >> sx >> sy >> ex >> ey;
        s[sx][sy].insert({ ex,ey });
        s[ex][ey].insert({ sx,sy });
    }
    memset(dp, -1, sizeof(dp));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(0, 0) << '\n';
    
    return 0;
}
 cs

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

boj 14700 넴모넴모 (Hard)  (0) 2021.06.22
boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18

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

 

4781번: 사탕 가게

각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개

www.acmicpc.net

 

배낭문제로 해결할 수 있는 문제입니다.

 

가격 정보가 소수점 둘째자리까지 주어지므로 정수로 바꿔서 계산하였습니다.

다만 문제점은 반올림을 하기 위해 * 100 + 0.5를 해줘야한다는 점입니다.

 

 

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>
#include <cstring>
using namespace std;
typedef long long ll;
 
pair<int, int> list[5001];
ll dp[10001];
int N, M;
 
void func() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= M; j++) {
            if (list[i].second > j) continue;
 
            dp[j] = max(dp[j], dp[j - list[i].second] + list[i].first);
        }
    }
 
    cout << dp[M] << '\n';
}
 
void input() {
    double d;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> d;
        list[i].second = d * 100 + 0.5;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    double d;
    while (1) {
        cin >> N >> d;
        M = d * 100 + 0.5;
        if (!N) return 0;
 
        input();
        func();
        memset(dp, 0, sizeof(dp));
    }
}
 cs

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

boj 1311 할 일 정하기 1  (0) 2021.06.21
boj 1577 도로의 개수  (0) 2021.06.20
boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 1563 개근상  (0) 2021.06.02

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

 

2186번: 문자판

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의

www.acmicpc.net

영어 단어가 "BREAK"처럼 주어지면 문자 판에서 "BREAK"라는 글자가 몇 번 나오는지 구하는 문제입니다.

일단 기본적으로 dfs를 통해 구해주시면 되고, 모든 위치에서 시작할 수 있으니 단어의 첫 알파벳과 일치하는 위치를 시작으로 dfs를 돌려줍니다.

 

하지만 이 문제는 이동 방법이 상하좌우로 K칸까지 이동할 수 있으므로 훨씬 많은 이동이 발생하므로 dp를 같이 사용해줍니다.

dp[x][y][idx] : (x, y)에 도달하였을 때 현재 찾고자 하는 단어의 인덱스가 idx인 경우의 수

이렇게 놓을 수 있습니다.

 

문제의 답은 int범위라고 명시되어 있기때문에 long long은 사용하지 않아도 됩니다.

 

dp를 사용하지 않으면 시간초과가 발생하므로 dp는 필수입니다!!

 

 

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
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
 
string str;
char list[110][110];
int dp[100][100][81];
int direct[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int N, M, K, strLength;
 
int dfs(int x, int y, int idx) {
    if (idx == strLength) return 1;
 
    int &ret = dp[x][y][idx];
    if (ret != -1) return ret;
    ret = 0;
 
    for (int i = 0; i < 4; i++) {
        for (int j = 1; j <= K; j++) {
            int nx = x + direct[i][0] * j;
            int ny = y + direct[i][1] * j;
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] != str[idx]) continue;
 
            ret += dfs(nx, ny, idx + 1);
        }
    }
 
    return ret;
}
 
void func() {
    int ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j] != str[0]) continue;
 
            ans += dfs(i, j, 1);
        }
    }
 
    cout << ans << '\n';
}
 
void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
        }
    }
    cin >> str;
    strLength = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}
 cs

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

boj 1577 도로의 개수  (0) 2021.06.20
boj 4781 사탕 가게  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 1563 개근상  (0) 2021.06.02
boj 10800 컬러볼  (0) 2021.04.09

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

 

13325번: 이진 트리

입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가

www.acmicpc.net

루트에서 모든 리프노드 까지의 거리가 모두 같게만든 후 모든 가중치의 합의 최소를 구하는 문제입니다.

 

입력으로 주어지는 트리는 무조건 포화 이진 트리(perfect binary tree)이고,

이 문제는 독특하게 노드가 아닌 간선만 입력으로 주어집니다.

 

높이가 1이면 2개의 가중치, 2면 4개의 가중치이므로 높이 N에는 2^N개의 가중치가 있다는 것을 알 수 있습니다.

따라서 입력으로 2가 주어지면 높이가 1인 가중치(2) + 2인 가중치(4) = 총 6개를 입력으로 받습니다.

 

이 문제는 리프에서부터 같은 부모로 이어지는 간선 두개를 비교하여 합을 같게 맞추는 식으로 루트까지 올라가면서 계산하는 방식으로 해결할 수 있습니다.

 

 

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

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

boj 4781 사탕 가게  (0) 2021.06.19
boj 2186 문자판  (0) 2021.06.19
boj 1563 개근상  (0) 2021.06.02
boj 10800 컬러볼  (0) 2021.04.09
boj 12869 뮤탈리스크  (0) 2021.04.04

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

 

1563번: 개근상

백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독

www.acmicpc.net

점화식 구하는게 좀 복잡할 수도 있는 dp문제입니다.

문제를 풀고나서 다른분들의 풀이를 보니 3차원배열을 사용하셨던데 저는 2차원 dp배열로 해결하였습니다.

 

우선 이 문제는 지각을 두 번 이상 하거나, 결석을 세 번 연속으로 하는 경우를 제외한 모든 경우의 수를 구해야합니다.

 

손으로 직접 그려본 후에 점화식을 찾았습니다.

dp[N][start] : 학기 첫날(start)이 출석 / 지각 / 결석일 때 N번째 날의 경우의 수

		[0]	[1]	[2]	sum
N = 1	 1	1	1	3

N = 2	 3	2	3	8

N = 3	 8	4	7	19

N = 4	 19	7	17	43

N = 5	 43	13	38	94

N = 6	 94	24	82	200

 

dp[N][0] : 첫날이 출석인 경우의 수

 -> dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]

dp[N][1] : 첫날이 지각인 경우의 수

 -> dp[N - 1][1] + dp[N - 2][1] + dp[N - 3][1]

dp[N][2] : 첫날이 결석인 경우의 수

 -> dp[N - 1][0] + dp[N - 1][1] + dp[N - 2][0] + dp[N - 2][1]

 

출력은 dp[N][0 ~ 2]를 더해 1000000으로 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
#include <iostream>
#define MOD 1000000
using namespace std;
 
int dp[1001][3];
int N;
 
void init() {
    dp[0][1] = 1;
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;
    dp[2][0] = 3;
    dp[2][1] = 2;
    dp[2][2] = 3;
    for (int i = 3; i <= 1000; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
        dp[i][1] = (dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]) % MOD;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 2][0] + dp[i - 2][1]) % MOD;
    }
}
 
void input() {
    cin >> N;
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % MOD << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
 
    return 0;
}
 cs

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

boj 2186 문자판  (0) 2021.06.19
boj 13325 이진 트리  (0) 2021.06.18
boj 10800 컬러볼  (0) 2021.04.09
boj 12869 뮤탈리스크  (0) 2021.04.04
boj 1520 내리막 길  (0) 2021.03.28

+ Recent posts

티스토리툴바