반응형

www.acmicpc.net/problem/2579

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int arr[301];
int dp[301];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    dp[0] = 0;
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
 
    for (int i = 3; i <= n; i++) 
        dp[i] = max(arr[i - 1] + dp[i - 3], dp[i - 2]) + arr[i];
    
    cout << dp[n];
}
cs
반응형

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

백준 9095  (0) 2021.02.15
백준 1520 [복습 필수]  (0) 2021.01.30
백준 2565  (0) 2021.01.28
백준 9251  (0) 2021.01.27
백준 11053  (0) 2021.01.27
반응형

www.acmicpc.net/problem/2565

 

2565번: 전깃줄

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

www.acmicpc.net

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
63
64
#include <iostream>
#include <algorithm>
#include <vector>
#define pii pair<int, int>
using namespace std;
pii arr[101];
vector<vector<int> > v(501);
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> arr[i].first >> arr[i].second;
            
    // pair의 first 기준 정렬
    sort(arr, arr + n);
 
    // second 값이 더 작으면 2차원 벡터에 삽입
    int cnt = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i].second < arr[j].second) {
                v[arr[i].first].push_back(arr[j].first);
                v[arr[j].first].push_back(arr[i].first);
                cnt++;
            }
        }
    }
 
    int ans = 0;
    while (cnt > 0) {
        int max_size = 0;
        int max_idx = 0;
        // size 가장 큰 인덱스 찾기
        for (int i = 0; i<v.size(); i++){
            if (!v[i].empty()) {
                if ((int)v[i].size() > max_size) {
                    max_size = (int)v[i].size();
                    max_idx = i;
                }
            }
        }
 
        // 해당 인덱스 값을 2차원 벡터에서 제거
        for (int i = 0; i < v[max_idx].size(); i++) {
            int cur_idx = v[max_idx][i];
            
            // 해당 인덱스 값의 위치 찾아서 제거
            for (auto it = v[cur_idx].begin(); it != v[cur_idx].end(); it++) {
                if (*it == max_idx) {
                    v[cur_idx].erase(it);
                    cnt--;
                    break;
                }
            }
        }
        // 해당 인덱스의 벡터 초기화
        v[max_idx].clear();
        ans++;
    }
    cout << ans;
}
 cs

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define pii pair<int, int>
using namespace std;
pii arr[101];
int arr2[101];
int dp[101];
vector<vector<int> > v(501);
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) 
        cin >> arr[i].first >> arr[i].second;
    sort(arr, arr + n);
 
    int cnt = 0;
    for (int i = 0; i < n; i++)
        dp[i] = 1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[j].second > arr[i].second) {
                dp[j] = max(dp[i] + 1, dp[j]);
                cnt = max(cnt, dp[j]);
            }
        }
    }
    cout << n-cnt;
}    
cs
반응형

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

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 9251  (0) 2021.01.27
백준 11053  (0) 2021.01.27
백준 12865  (0) 2021.01.26
반응형

www.acmicpc.net/problem/9251

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

같으면 dp[i][j] = dp[i-1][j-1] + 1

다르면 dp[i][j] = max(dp[i][j-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
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][1001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    string a, b;
    cin >> a >> b;
 
    int max_length = 0;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
 
            max_length = max(max_length, dp[i][j]);
        }
    }
    cout << max_length;
}
 cs

참고: 2020-1 문제 해결 기법 8주차 2번

8B(LCS) 설명 12161567_박기수.pptx
0.45MB

반응형

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

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 11053  (0) 2021.01.27
백준 12865  (0) 2021.01.26
반응형

www.acmicpc.net/problem/11053

 

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

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

www.acmicpc.net

DP 배열 2차원으로 하면 반례 생김

4

10 40 20 30

이중 for문 돌면서 기준 값(arr[i])보다 현재 값(arr[j])이 클 경우

증가시킬 지(dp[j] = dp[i] + 1) 말 지(dp[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
#include <iostream>
using namespace std;
int arr[1001];
int dp[1001];
int n;
int max_length = 0;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            // 갱신할 지 말 지 선택
            if (arr[j] > arr[i])
                dp[j] = (dp[i] + 1 > dp[j]) ? dp[i] + 1 : dp[j];
        }
        // 최대 길이 갱신
        max_length = max_length > dp[i] ? max_length : dp[i];
    }
    cout << max_length + 1;
}
 cs
반응형

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

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 9251  (0) 2021.01.27
백준 12865  (0) 2021.01.26
반응형

www.acmicpc.net/problem/13305

 

13305번: 주유소

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1

www.acmicpc.net

 

1. 현재 도시의 가격(price[i])와 현재 최솟값(min) 비교

  -> 현재 도시의 가격이 더 싸면 min = price[i]

 

2. 계산은 무조건 해야함

  -> total_price = min * dist[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
#include <iostream>
#define ll long long
using namespace std;
ll dist[100000];
ll price[100000];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0; i < n-1; i++)
        cin >> dist[i];
 
    for (int i = 0; i < n; i++)
        cin >> price[i];
 
    int minIdx = 0;
    ll min = price[0];
 
    ll total_price = 0;
    for (int i = 0; i < n; i++) {
        if (price[i] < min) 
            min = price[i];
        total_price += min * dist[i];
    }
    cout << total_price;
}
 cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 1715  (0) 2021.02.05
백준 1080  (0) 2021.02.05
백준 1946  (0) 2021.02.05
백준 2812  (0) 2021.02.04
백준 11509  (0) 2021.01.26
반응형

www.acmicpc.net/problem/11509

 

11509번: 풍선 맞추기

첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다.

www.acmicpc.net

방법 1. 배열 이용 -> 코드 짧음

방법 2. map 이용 -> 메모리 절약

 

입력한 값을 별도의 배열에 저장

이전에 입력된 값 목록에서 (현재 값+1)이 있는지 확인해야 함 -> 하나의 화살로 연속해서 터뜨림

 

단순하게 현재 입력한 값(1) 보다 더 큰 값(2)이 있는지만 확인하면

"2 1 1 1 1" 같은 반례 찾지 못함

현재 입력한 값(1) 보다 더 큰 값(2)이 “몇 개“ 있는지까지 확인해야 함

 

더 큰 값이 없으면 새로운 화살을 사용해야 하므로 cnt++

배열 사용: 코드 짧음 (메모리: 5924KB)

1.x 추가: arr[x]++;

2. x+1 확인

  1) x+1 == 0: cnt++;

  2) x+1 > 0: m[x+1]--;

map 사용: 메모리 적게 사용 (메모리: 2152KB)

1.x 있음: m[x]++;

    x 없음: m.insert({x, 1});

2. x+1 없음 or 0: cnt++;

   x+1 > 0: m[x+1]--;

방법 1. 배열 이용

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
int arr[1000001];
int main() {
    int n, x, cnt = 0;
    cin >> n;
    while(n--) {
        cin >> x;
        arr[x]++;
        arr[x + 1] == 0 ? cnt++ : arr[x + 1]--;
    }
    cout << cnt;
}
 cs

방법 2. map 이용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <map>
using namespace std;
map<int, int> m;
int main() {
    int n, x, cnt = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
 
        if (m.find(x) == m.end())
            m.insert({ x, 1 });
        else
            m[x]++;
 
        if ((m.find(x + 1) == m.end()) || m[x + 1] == 0)
            cnt++;
        else
            m[x + 1]--;
    }
    cout << cnt;
}
 cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 1715  (0) 2021.02.05
백준 1080  (0) 2021.02.05
백준 1946  (0) 2021.02.05
백준 2812  (0) 2021.02.04
백준 13305  (0) 2021.01.27
반응형

www.acmicpc.net/problem/12865

 

12865번: 평범한 배낭

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)

www.acmicpc.net

 

 

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 <algorithm>
using namespace std;
 
int weight[101];
int value[101];
int dp[101][100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
        
    int N, K;
    cin >> N >> K;
    for (int i = 1;i <= N;i++) {
        cin >> weight[i] >> value[i];
    }
 
    // 목표: 무게를 j로 만들기
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            // 현재 물건 못 넣음
            if (weight[i] > j)
                dp[i][j] = dp[i - 1][j];
 
            // 현재 물건 넣을 수 있음
            else
                dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i-1][j]);
        }
    }
    cout << dp[N][K];
}
 cs

참고: (2020-1) 문제 해결 기법 9주차 2번

반응형

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

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 9251  (0) 2021.01.27
백준 11053  (0) 2021.01.27
반응형

www.acmicpc.net/problem/11286

방법 1. priority queue 두개 사용 (양수 / 음수)

방법 2. pair<int, int> 사용

방법 3. 정렬을 위한 cmp 구조체 사용

 

1. priority 두개 사용

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 <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq_pos;
priority_queue<int> pq_neg;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if (x == 0) {
            if (pq_pos.empty()) {
                // 1. 둘 다 비었음
                if (pq_neg.empty())
                    cout << 0 << '\n';
 
                // 2. 양수pq (x), 음수pq(o)
                else {
                    cout << pq_neg.top() << '\n';
                    pq_neg.pop();
                }
            }
            else {
                // 3. 양수pq (o), 음수pq(x)
                if (pq_neg.empty()) {
                    cout << pq_pos.top() << '\n';
                    pq_pos.pop();
                }
                // 4. 둘 다 있음
                else {
                    if (pq_pos.top() < -pq_neg.top()) {        // 2 vs -3: 양수 출력
                        cout << pq_pos.top() << '\n';        // 2 vs -2: 음수 출력
                        pq_pos.pop();                        // 2 vs -1: 음수 출력
                    }
                    else {
                        cout << pq_neg.top() << '\n';
                        pq_neg.pop();
                     }
                }
            }
        }
        else {
            if (x > 0)
                pq_pos.push(x);
            else
                pq_neg.push(x);
        }
    }
}
 cs

 

2. pair<int, int> 사용

정렬 기준

1순위: 첫 번째 (절대값)

2순위: 두 번째 (원래값)

 

(2, -2)       (1, -1)

(1, -1)       (1, 1)

(1, 1)    -> (2, -2)

(2, 2)        (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
#include <iostream>
#include <queue>
#define pii pair<int, int>
using namespace std;
priority_queue<pii, vector<pii>, greater<pii> > pq;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if (x == 0) {
            if (pq.empty())
                cout << 0 << '\n';
            else {
                cout << pq.top().second << '\n';
                pq.pop();
            }
        }
        else {
            pq.push({ abs(x), x });
        }
    }
}
 cs

 

3. 정렬을 위한 cmp 구조체 사용

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
#include <iostream>
#include <queue>
using namespace std;
struct cmp {
    bool operator()(int a, int b) {
        if (abs(a) == abs(b))
            return a > b;
        return abs(a) > abs(b);
    }
};
priority_queue<int, vector<int>, cmp > pq;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) {
        int x;
        cin >> x;
        if (x == 0) {
            if (pq.empty())    
                cout << 0 << '\n';
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else {
            pq.push(x);
        }
    }
}
cs
반응형

'백준 > 우선순위큐' 카테고리의 다른 글

백준 1655 [복습필수]  (0) 2021.07.11

+ Recent posts

티스토리툴바