반응형

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

 

2056번: 작업

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 작업이 끝나는 시간을 저장할 cost 배열을 만듭니다.

 

2. 선행 작업이 모두 자신보다 숫자가 작은 작업이므로 앞에서 진행된 작업 중 가장 늦게 끝난 작업에 해당 작업이 끝나는데 걸리는 시간을 더해 cost에 저장해줍니다.

 

3. cost 배열에서 가장 큰 값을 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
int cost[10001];
int ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        int c, n;
        scanf("%d %d", &c, &n);
        if (n == 0) cost[i] = c;
        for (int j = 0; j < n; j++) {
            int task;
            scanf("%d", &task);
            cost[i] = max(cost[i], cost[task] + c);
        }
        ans = max(ans, cost[i]);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 6497번 - 전력난 (C++)  (0) 2023.02.22
[ 백준 ] 18223번 - 민준이와 마산 그리고 건우 (C++)  (0) 2023.02.21
[ 백준 ] 2406번 - 안정적인 네트워크 (C++)  (0) 2023.02.19
[ 백준 ] 20010번 - 악덕 영주 혜유 (C++)  (0) 2023.02.18
[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
반응형

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

 

1937번: 욕심쟁이 판다

n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 대나무 숲을 저장할  arr 배열과, 메모이제이션을 위한 dp 배열을 만듭니다.

 

2. dp[ i ][ j ]에는 i, j 좌표에서 시작했을 때 가장 많이 이동할 수 있는 칸의 수를 저장합니다.

 

3. 따라서, 한번 저장한 좌표에는 다시 갈 필요가 없으므로 dp[ i ][ j ] != 0일 때 dp[ i ][ j ]를 return 합니다.

 

4. 그렇지 않다면 arr[ yy ][ xx ] > arr[ y ][ x ] 일 때, dp[ y ][ x ] = max(dp[ y ][ x ], dfs(yy, xx) + 1)의 점화식을 이용하여 각 좌표의 최댓값을 저장해 줍니다.

 

5. 모든 좌표를 2중 for문을 이용해 돌며 dfs를 실행하고, 그중 최댓값을 ans에 저장합니다.

 

6. 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
#include<iostream>
 
using namespace std;
 
int n;
int arr[500][500];
int dp[500][500];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int ans;
 
int dfs(int y, int x)
{
    int& ret = dp[y][x];
    if (ret != 0) return ret;
    ret = 1;
    
    for (int i = 0; i < 4; i++) {
        int yy = y + dy[i];
        int xx = x + dx[i];
 
        if (yy >= 0 && yy < n && xx >= 0 && xx < n) {
            if (arr[yy][xx] > arr[y][x]) {
                ret = max(ret, dfs(yy, xx) + 1);
            }
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = max(ans,dfs(i, j));
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1944번 - 복제 로봇 (C++)  (0) 2023.02.17
[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
반응형

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

 

7570번: 줄 세우기

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 어린이가 항상 맨 뒤나 맨 앞으로 가야 하므로 일반적인 증가하는 부분 수열이 아닌 연속으로 증가하는 최장 부분 수열을 찾아야 합니다. ex) 2, 4, 7 (x)     3, 4, 5 (o)

 

2. 겹치는 수가 없기 때문에 cnt 배열을 통해 각각의 수가 몇번 째 증가하는 수인지를 저장합니다.

 

3. cnt[ i ] = cnt[ arr[ i ] - 1 ]+1의 점화식을 활용하여 값을 저장해 줍니다.

 

4. ans = max(ans, cnt[ i ])를 통해 최장 연속 증가 부분 수열의 길이를 저장합니다.

 

5. N - 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
#include<iostream>
 
using namespace std;
 
int N;
int arr[1000000];
int cnt[1000001];
int ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 0; i < N; i++) {
        cnt[arr[i]] = cnt[arr[i] - 1] + 1;
        ans = max(ans, cnt[arr[i]]);
    }
 
    printf("%d", N - ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11
반응형

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

 

2565번: 전깃줄

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. pair<int, int> arr 배열을 만들어서 입력받은 A전봇대와 B전봇대를 저장합니다.

 

2. A전봇대의 번호를 기준으로 오름차순으로 정렬합니다.

 

3. lower_bound를 이용하여 LIS의 길이를 구하고, N - LIS.size()를 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<algorithm>
 
using namespace std;
 
int N;
vector<int> LIS;
pair<int, int> arr[100];
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int A, B;
        scanf("%d %d", &A, &B);
        arr[i] = { A,B };
    }
 
    sort(arr, arr + N);
 
    LIS.push_back(arr[0].second);
 
    for (int i = 1; i < N; i++) {
        if (LIS[LIS.size() - 1] < arr[i].second) {
            LIS.push_back(arr[i].second);
        }
        else {
            auto it = lower_bound(LIS.begin(), LIS.end(), arr[i].second);
            *it = arr[i].second;
        }
    }
 
    printf("%d", N - (int)LIS.size());
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 7570번 - 줄 세우기 (C++)  (0) 2023.02.14
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11
[ 백준 ] 15971번 - 두 로봇 (C++)  (0) 2023.02.10
[ 백준 ] 2637번 - 장난감 조립 (C++)  (0) 2023.02.09
반응형

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

 

2637번: 장난감 조립

첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/72

 

[ 알고리즘 ] 위상 정렬 알고리즘(Topological Sort Algorithm)

1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란? 위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방

rudalsd.tistory.com

 

1. 완제품에서부터 부품 쪽으로 내려가면서 개수를 저장해야 하므로, X -> Y 방향으로 단방향 그래프를 만들어줍니다.

 

2. 1과 동시에 중간 부품이 몇 번 필요한지 in [ Y ]++를 통해 저장해 주고, basic [ X ] = 1을 통해 기초 부품인지 아닌지 체크해 줍니다.

 

3. 위상정렬을 통해 N번부터 ans 배열에 필요한 부품의 개수를 저장합니다.

 

4. 하위 부품의 개수는 ans [next] += ans [cur] * next.cnt로 저장합니다.

 

5. basic [ i ] != 1인 부품에 대해서 ans [ i ]를 출력해 줍니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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<vector>
#include<queue>
 
using namespace std;
 
int N, M;
vector<pair<int, int>> list[101];
int ans[101];
int basic[101];
int in[101];
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int X, Y, K;
        scanf("%d %d %d", &X, &Y, &K);
        list[X].push_back({ Y,K });
        basic[X] = 1;
        in[Y]++;
    }
 
    queue<int> q;
    q.push(N);
    ans[N] = 1;
 
    while (!q.empty()) {
        const int cur = q.front();
        q.pop();
 
        for (auto& next : list[cur]) {
            ans[next.first] += ans[cur] * next.second;
            in[next.first]--;
            if (in[next.first] == 0) {
                q.push(next.first);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        if (basic[i] != 1) {
            printf("%d %d\n", i, ans[i]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11
[ 백준 ] 15971번 - 두 로봇 (C++)  (0) 2023.02.10
[ 백준 ] 11658번 - 구간 합 구하기 3 (C++)  (0) 2023.02.08
[ 백준 ] 2458번 - 키 순서 (C++)  (0) 2023.02.07
[ 백준 ] 2211번 - 네트워크 복구 (C++)  (0) 2023.02.06
반응형

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

 

17090번: 미로 탈출하기

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited [ 501 ][ 501 ] 배열을 만들어서 -1로 초기화합니다.

 

2. dfs를 통해 해당 좌표에 방문 시 visited배열이 -1이 아니라면 그 값을  return 합니다.

 

3. visited 배열을 0으로 초기화시키고, 지도에 적힌 문자대로 이동합니다.

 

4. 이동했을 때 지도 밖으로 나간다면 1을 return 하고, 그렇지 않다면 다시 재귀해 줍니다.

 

5. visited 배열에서 값이 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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int N, M;
char arr[501][501];
int visited[505][505];
 
int dfs(int r, int c)
{
    if (visited[r][c] != -1) return visited[r][c];
    visited[r][c] = 0;
 
    if (arr[r][c] == 'U') {
        if (r == 0) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r - 1, c);
    }
    else if (arr[r][c] == 'R') {
        if (c == M-1) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r, c + 1);
    }
    else if (arr[r][c] == 'D') {
        if (r == N - 1) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r + 1, c);
    }
    else {
        if (c == 0) return visited[r][c] = 1;
        else return visited[r][c] = dfs(r, c - 1);
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
    memset(visited, -1, sizeof(visited));
 
    for (int i = 0; i < N; i++) {
        scanf("%s", &arr[i]);
    }
 
    int ans = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] == -1) {
                if (dfs(i, j)) ans++;
            }
            else if (visited[i][j] == 1) ans++;
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 13418번 - 학교 탐방하기 (C++)  (0) 2023.01.29
[ 백준 ] 16398번 - 행성 연결 (C++)  (0) 2023.01.28
[ 백준 ] 14923번 - 미로 탈출 (C++)  (0) 2023.01.26
[ 백준 ] 5558번 - チーズ (Cheese) (C++)  (0) 2023.01.25
[ 백준 ] 3770번 - 대한민국 (C++)  (0) 2023.01.24
반응형

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

 

2550번: 전구

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은

www.acmicpc.net

 

 

[ 문제풀이 ]

 

글을 읽기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. 스위치를 순서대로 저장할 배열과 스위치의 위치를 저장할 배열을 각각 만들어 값을 저장합니다.

 

2. 전구의 위치를 저장할 배열을 만들어 값을 저장합니다.

 

3. lower_bound를 이용해 LIS를 만들고, 각각의 스위치가 LIS에서 몇 번째 idx에 있는지 idx 배열을 만들어 값을 저장합니다.

 

4. idx 배열의 끝에서부터 for문을 돌면서 LIS에 들어갈 스위치를 ans 배열에 저장합니다.

 

5. ans 배열을 정렬합니다.

 

6. LIS의 size를 출력하고, 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
int sw[10001];        //sw[i] = 스위치 번호
int pos[10001];        //pos[스위치 번호] = i
int bulb[10001];    //전구의 순서
int idx[10001];        //LIS에서 몇번 째 위치해 있는지 저장할 배열
vector<int> LIS;
vector<int> ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int idx;
        scanf("%d", &idx);
        sw[i] = idx;
        pos[idx] = i;
    }
 
    for (int i = 0; i < N; i++) {
        int idx;
        scanf("%d", &idx);
        bulb[pos[idx]] = i;
    }
 
    LIS.push_back(bulb[0]);
    idx[0] = 1;
 
    for (int i = 1; i < N; i++) {        //lower_bound
        if (bulb[i] > LIS[LIS.size() - 1]) {
            LIS.push_back(bulb[i]);
            idx[i] = LIS.size();
        }
        else {
            auto it = lower_bound(LIS.begin(), LIS.end(), bulb[i]);
            *it = bulb[i];
            idx[i] = it - LIS.begin() + 1;    //현재 스위치의 LIS에서의 위치
        }
    }
 
    int cur = LIS.size();
 
    for (int i = N - 1; i >= 0; i--) {
        if (idx[i] == cur) {
            ans.push_back(sw[i]);
            cur--;
        }
    }
 
    sort(ans.begin(), ans.end());
 
    printf("%d\n", LIS.size());
 
    for (int i = 0; i < LIS.size(); i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1669번 - 멍멍이 쓰다듬기 (C++)  (0) 2022.11.30
[ 백준 ] 11967번 - 불켜기 (C++)  (0) 2022.11.29
[ 백준 ] 17182번 - 우주 탐사선 (C++)  (0) 2022.11.27
[ 백준 ] 15591번 - MooTube (Silver) (C++)  (0) 2022.11.26
[ 백준 ] 4991번 - 로봇 청소기 (C++)  (0) 2022.11.25
반응형

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

 

2281번: 데스노트

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp [ i ][ j ]에서 i는 현재 이름의 idx, j는 현재 줄에 쓰인 이름의 길이입니다.

 

2. 현재 idx의 이름을 현재 줄에 적을지 다음 줄에 적을지 선택하여 재귀 함수를 돌려줍니다.

 

3. dp[1][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
#include<iostream>
#include<cstring>
 
using namespace std;
 
int n, m;
int name[1001];
int dp[1001][1001];    //i번 이름, 해당 줄에 지금까지 쓰인 글자 수
 
 
int go(int idx, int len)    //len = 가장 뒤의 공백 포함
{
    if (idx > n) return 0;
 
    int& ret = dp[idx][len];
    if (ret != -1) return ret;
 
    //다음 줄에 쓰는 경우
    ret = (m - len + 1) * (m - len + 1) + go(idx + 1, name[idx] + 1);
 
    //현재 줄에 쓰는 경우
    if (len + name[idx] <= m) {
        ret = min(ret, go(idx + 1, len + name[idx] + 1));
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &name[i]);
    }
 
    memset(dp, -1, sizeof(dp));
 
    printf("%d", go(1, 0));
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 1976번 - 여행 가자 (C++)  (0) 2022.11.11
[ 백준 ] 12286번 - 돌 그룹 (C++)  (0) 2022.11.10
[ 백준 ] 7569번 - 토마토 (C++)  (0) 2022.11.08
[ 백준 ] 2195번 - 문자열 복사 (C++)  (0) 2022.11.07
[ 백준 ] 2253번 - 점프 (C++)  (0) 2022.11.06
반응형

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

 

2253번: 점프

N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. dp [ i ][ j ]에서 i는 현재 돌의 번호, j는 x의 값입니다.

 

2. 다음과 같은 점화식을 세웁니다.

dp[ i ][ j ] = min(dp [ i ][ j ], go(i + xx, xx) + 1)

 

3. 2에서 xx는 j + 1, j - 1( > 0), 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
46
47
48
49
50
51
52
53
#include<iostream>
 
using namespace std;
 
int N, M;
int m[10001];
int dp[10001][150];
 
int go(int cur, int x)
{
    if (cur == N) return 0;
 
    int& ret = dp[cur][x];
    if (ret != 0) return ret;
    
    ret = 987654321;
 
    for (int i = -1; i < 2; i++) {
        int xx = x + i;
 
        if (xx > 0 && cur + xx <= N && m[cur + xx] != 1) {
            ret = min(ret, go(cur + xx, xx) + 1);
        }
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int num;
        scanf("%d", &num);
 
        m[num] = 1;
 
        if (m[2] == 1) {
            printf("%d", -1);
            return 0;
        }
    }
 
    go(1, 0);
 
    if (dp[1][0] == 987654321) {
        printf("%d", -1);
    }
    else {
        printf("%d", dp[1][0]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 7569번 - 토마토 (C++)  (0) 2022.11.08
[ 백준 ] 2195번 - 문자열 복사 (C++)  (0) 2022.11.07
[ 백준 ] 14002번 - 가장 긴 증가하는 부분 수열 4 (C++)  (0) 2022.11.05
[ 백준 ] 1577번 - 도로의 개수 (C++)  (0) 2022.11.04
[ 백준 ] 2229번 - 조 짜기 (C++)  (0) 2022.11.03
반응형

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

 

14002번: 가장 긴 증가하는 부분 수열 4

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/175?category=1064608 

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면

rudalsd.tistory.com

 

1. order배열에 각 수의 LIS에서의 위치를 저장합니다.

 

2. order배열의 끝에서부터 처음까지 for문을 통해 LIS의 cnt = 길이의 숫자로 갱신해주고, order [ i ] == cnt를 만나면 ans에 저장해주고, cnt--를 해줍니다.

 

3. 마지막에 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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N;
int arr[1000];
int order[1000];    //헤당 idx의 숫자의 LIS에서의 순서
vector<int> ans;    //최장 부분 증가 수열
vector<int> LIS;    //lower_bound
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    LIS.push_back(arr[0]);
    order[0] = 1;
 
    for (int i = 1; i < N; i++) {
        if (LIS[LIS.size() - 1] < arr[i]) {
            LIS.push_back(arr[i]);
            order[i] = LIS.size();
        }
        else {
            auto it = lower_bound(LIS.begin(), LIS.end(), arr[i]);
            int idx = it - LIS.begin();
            *it = arr[i];
            order[i] = idx + 1;
        }
    }
 
    int cnt = LIS.size();
 
    printf("%d\n", LIS.size());
 
    for (int i = N - 1; i >= 0; i--) {
        if (order[i] == cnt) {
            ans.push_back(arr[i]);
            cnt--;
        }
    }
 
    for (int i = ans.size() - 1; i >= 0; i--) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 2195번 - 문자열 복사 (C++)  (0) 2022.11.07
[ 백준 ] 2253번 - 점프 (C++)  (0) 2022.11.06
[ 백준 ] 1577번 - 도로의 개수 (C++)  (0) 2022.11.04
[ 백준 ] 2229번 - 조 짜기 (C++)  (0) 2022.11.03
[ 백준 ] 2157번 - 여행 (C++)  (0) 2022.11.02

+ Recent posts

티스토리툴바