'알고리즘' 카테고리의 글 목록 (9 Page)

알고리즘

백준 2252 줄 세우기 쉬운 풀이(C++/CPP) 2021.02.07
[알고리즘] Topological Sort, 위상정렬 2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP) 2021.02.07
백준 14226 이모티콘 2021.02.06
백준 1744 수 묶기 쉬운 풀이(C++/CPP) 2021.02.06
백준 1963 소수 경로 2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) 2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP) 2021.02.06
백준 2225 합분해 쉬운 풀이 2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP) 2021.02.04

백준 2252 줄 세우기 쉬운 풀이(C++/CPP)

2021. 2. 7. 15:19

문제링크 : https://www.acmicpc.net/problem/1520

문제 접근

Topological Sort 기본문제
개념 참조 : https://dev-jango.tistory.com/12

시간복잡도 계산

모든 노드 : V
- 모든 노드에 인접한 노드의 indeg 감소 : E
- O(V + E)
- e4 + e5

인트 계산

숫자범위 생각할 숫자 없음

코드

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 <queue>
#include <vector>
 
using namespace std;
 
// 각 노드의 인접 리스트
vector<int> adj[32010];
// 각 노드에 들어오는 간선 개수
int indeg[32010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        // 인접한 간선 추가
        adj[a].push_back(b);
        // 들어오는 간선의 개수 증가
        indeg[b]++;
        
    }
    
    queue<int> q;
    for(int i=1; i<=N; i++) {
        if(indeg[i]==0) q.push(i);
    }
    
    vector<int> rs;
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        rs.push_back(eq);
        
        for(int x : adj[eq]) {
            // 들어오는 간선의 개수 감소
            indeg[x]--;
            // 만약 들어오는 간선의 개수가 0일때 큐에 추가
            if(indeg[x] == 0) q.push(x);
        }
    }
    
    for(int ers : rs) cout << ers << ' ';
    
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

topological sort

비슷한 문제

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

백준 1786 찾기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 5052 전화번호 목록 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 14226 이모티콘 (0)	2021.02.06
백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06

[알고리즘] Topological Sort, 위상정렬

2021. 2. 7. 15:17

문제 정의

일부 노드들의 순서가 주어졌을때, 전체 순서를 정하는 문제

문제 접근

노드 순서를 인접 리스트(adj)로 저장
- 인접 리스트로 저장하면서, 노드에 들어오는 간선의 개수(indeg)를 기록
- 큐를 하나 생성해서, indeg가 0인 것들을 추가
  - indeg가 0이란 의미 : 들어오는 간선이 없으므로, 출발노드
- 각 큐에 들어있는 노드에 대해서 다음을 반복
  - 결과 리스트에 추가
  - 각 노드에 인접한 노드들에 대해, indeg를 감소
  - 이떄, indeg가 0인 노드는 큐에 새로 추가
- 결과 리스트 출력

시간복잡도

모든 노드 : V
- 모든 노드에 인접한 노드의 indeg 감소 : E
- O(V + E)

인트 계산

모든 입력 >> 10억 이하의정음수 >> INT 가능
dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용

대표예제 : 백준 2252 줄세우기

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 <queue>
#include <vector>
 
using namespace std;
 
// 각 노드의 인접 리스트
vector<int> adj[32010];
// 각 노드에 들어오는 간선 개수
int indeg[32010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        // 인접한 간선 추가
        adj[a].push_back(b);
        // 들어오는 간선의 개수 증가
        indeg[b]++;
        
    }
    
    queue<int> q;
    for(int i=1; i<=N; i++) {
        if(indeg[i]==0) q.push(i);
    }
    
    vector<int> rs;
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        rs.push_back(eq);
        
        for(int x : adj[eq]) {
            // 들어오는 간선의 개수 감소
            indeg[x]--;
            // 만약 들어오는 간선의 개수가 0일때 큐에 추가
            if(indeg[x] == 0) q.push(x);
        }
    }
    
    for(int ers : rs) cout << ers << ' ';
    
    return 0;
}
 
Colored by Color Scripter
cs

비슷한 유형

몇번째 순서인지 구하는 문제
- topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
  - 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
  - 즉, 순서가 뒤틀리거나 틀리지만 않으면 됨
- 내가 정확히 몇번째 순서를 구하는 문제는 플로이드를 통해서 확인 가능
- https://www.acmicpc.net/problem/2458
- map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1

'알고리즘 > 개념' 카테고리의 다른 글

[알고리즘] Dijkstra, 다익스트라 알고리즘 (0)	2021.02.14
[알고리즘] Floyd Warshall, 플로이드 와샬 알고리즘 (0)	2021.02.08
[알고리즘] Minimum Spanning Tree, 최소 스패닝 트리 (0)	2021.02.08
[알고리즘] 문자열 KMP, Rabin Karp (0)	2021.02.07
[알고리즘] 문자열 TRIE (0)	2021.02.07

백준 2805 나무 자르기 쉬운 풀이(C++/CPP)

2021. 2. 7. 14:53

문제링크 : https://www.acmicpc.net/problem/2805

문제 접근

모든 높이를 기준으로, 전체 나무 순회 >> O(M*N) >> 2e9 * 1e6 >> 시간초과
자르려는 높이 증가할수록 얻을수 있는 나무의 길이가 감소 >> 선형적이므로 이진탐색 사용 가능
- 자르려는 높이를 이진탐색 O(lgM)
- 이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
- O(N*lgM)
Lower vs Upper
- 이진 탐색 하는것을 그래프로 그려봤을때
- X축 : 자르려는 높이, Y축 : 얻게되는 나무의 수
- 같은값이 없을때 더 낮은 높이를 설정해야함 > UpperBound
- 더 높은 높이를 설정할 경우, 얻게 되는 나무의 수가 부족한 현상 발생

시간복잡도 계산

자르려는 높이를 이진탐색 O(lgM)
이때 나무 순회하면서 얻을 수 있는 나무를 구함 >> O(N)
O(N*lgM)

인트 계산

이진탐색 시 필요한 나무길이 : 나무길이 최대 1e6 * 2e9 >> 2e15 >> 인트 사용 불가, long long
- 나무 높이 : 1e9 이하 >> 인트 사용 가능

코드

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>
 
using namespace std;
typedef long long ll;
 
int tree[1000010];
 
int N,M;
 
ll chk(int mid) {
    ll rs=0;
    for(int i=0; i<N; i++) {
        rs += max(tree[i]-mid, 0);
    }
    return rs;
}
 
int binsearch(int M, int st, int en) {
    if(st==en) return st;
    
    int mid = (st+en+1)/2;
    if(chk(mid) >= M) return binsearch(M, mid, en);
    else return binsearch(M, st, mid-1);
}
 
int main() {
    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> tree[i];
    
    cout << binsearch(M,0,1e9) << '\n';
    
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

이진탐색 - 케이스
- 이진 탐색 문제 중 정답이 되는 값을 이진탐색 하는 문제
- 이와 반대 유형으로 '이진탐색 - 모든 케이스'
  - 모든 케이스에 대해서, 연산을 이진탐색 해주는 유형

비슷한 문제

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

백준 5052 전화번호 목록 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 2252 줄 세우기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 14226 이모티콘 (0)	2021.02.06
백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06

백준 14226 이모티콘

2021. 2. 6. 14:50

문제링크 : https://www.acmicpc.net/problem/14226

문제 접근

BFS로 해서, 각 시간별 작업을 큐에 넣고 하면 되지 않을까
- 큐 : 화면, 클립보드
- 화면, 클립보드 중복 체크
  - 그래서 S개를 만드는데 시간 최소를 구하면 되지

시간복잡도 계산

BFS 시간복잡도 O(V+E) : 4e6
노드 : 화면 * 클립보드 1e6
간선: 3개 * 노드
O(V+E) : 4e6

인트 계산

S는 1000개 이하, 시간도 그보다 이하

코드

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 <queue>
#include <map>
using namespace std;
 
// 스티커가 1000개 이상으로갔다가 떨어질 수도 있음
// 범위를 정하기가 애매해서 map으로 정의
map<pair<int, int>, bool> chk;
int main() {
    int S; cin >> S;
    queue<pair<int, int>> q;
    
    q.push(make_pair(1,0));
    chk[make_pair(1,0)] = 1;
    int t=0;
    while(!q.empty()) {
        int qsize =q.size();
        
        while(qsize--) {
            auto eq = q.front(); q.pop();
            int sc = eq.first;
            int cl = eq.second;
            if(sc == S) {
                cout << t << '\n';
                return 0;
            }
            
            // 클립보드에 복사
            if(chk[make_pair(sc,sc)] == 0) {
                q.push(make_pair(sc, sc));
                chk[make_pair(sc,sc)] = 1;
            }
            // 클립보드에서 붙여쓰기
            if(chk[make_pair(sc+cl,cl)] == 0) {
                q.push(make_pair(sc+cl, cl));
                chk[make_pair(sc+cl,cl)] = 1;
            }
            // 하나 제거
            if(sc>0) {
                if(chk[make_pair(sc-1,cl)] == 0) {
                    q.push(make_pair(sc-1, cl));
                    chk[make_pair(sc-1,cl)] = 1;
                }
                
            }
            
        }
        t++;
    }
    
    
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

최소시간 구하는 BFS

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

백준 2252 줄 세우기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 2805 나무 자르기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) (0)	2021.02.06

백준 1744 수 묶기 쉬운 풀이(C++/CPP)

2021. 2. 6. 14:46

문제링크 : https://www.acmicpc.net/problem/1744

문제 접근

숫자끼리 더하거나 곱해서 최대로 나올수 있는 방법이 있음 >> 그리디
- 양수 : 큰수는 큰수끼리 곱해야함
- 음수 : 큰 음수끼리 곱해야함
- 0 :
  - 음수가 짝수일때 >> 그냥 더함
  - 음수가 홀수일때 >> 음수에 곱함
    - 예외 케이스
- 1곱하기 1인경우 >> 그냥 더하는게 나음
- -1곱하기 -1은 >> 곱하는게 나음

시간복잡도 계산

정렬한뒤 순차탐색 >> O(NlgN + N) >> O(NlgN) >> 20 * e5 = 2e6

인트 계산

정답은 항상 2^31 보다 작음 >> Int 가능?
근데 연산하는 중 수가 더 커질수도 있음
- 예시 : e4 * e4 가 5000쌍일경우
- 그래서 안전하게 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
ll nums[10010];
int main() {
    int N; cin >> N;
    int cntY=0, cntU=0, cnt1=0;
    for(int i=0; i<N; i++) {
        cin >> nums[i];
        if(nums[i] >1) cntY++;
        else if(nums[i] == 1) cnt1++;
        else if(nums[i] < 0) cntU++;
    }
    
    sort(nums, nums+N);
    ll rs=0;
    // 양수끼리 곱함
    bool sw = 0;
    ll tmp=0;
    for(int i=N-1; i>=N-cntY; i--) {
        // 양수 처음 더하면
        if(sw == 0) {
            sw = 1;
            tmp = nums[i];
        } else {
            sw = 0;
            rs += nums[i] * tmp;
            tmp = 0;
        }
    }
    
    if(sw == 1) {
        rs += tmp;
        tmp = 0;
        sw = 0;
    }
    rs += cnt1;
    
    sw = 0;
    tmp = 0;
    
    //음수끼리 곱함
    for(int i=0; i<N-cntY-cnt1; i++) {
        // 음수 처음이면
        if(sw == 0) {
            sw = 1;
            tmp = nums[i];
        } else {
            sw = 0;
            rs += nums[i] * tmp;
            tmp = 0;
        }
    }
    
    if(sw == 1) {
        // 만약 zero 있으면 더해서 0이므로 끝
        // 없으면 그냥 더함
        if(N == cntY + cntU + cnt1) {
            rs += tmp;
        }
        
    }
    
    cout << rs << '\n';
    
    
    return 0;
}
 
Colored by Color Scripter

cs

문제유형

그리디 - 숫자관련 최소 최대

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

백준 2805 나무 자르기 쉬운 풀이(C++/CPP) (0)	2021.02.07
백준 14226 이모티콘 (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP) (0)	2021.02.06

백준 1963 소수 경로

2021. 2. 6. 14:41

문제링크 : https://www.acmicpc.net/problem/1963

문제 접근

각 케이스를 변경하면서 최소횟수를 구하니까 BFS
- 각 자리수마다 한자리수만 바꿔서 소수가 될수있는것을 찾아서 큐에 넣어줌
- 이떄, 중복확인 체크 필요
- 그럼 소수인지 확인 여부는?, sqrt까지 나머지가 0되는게 있는지여부로 확인

시간복잡도 계산

BFS(V+E)
V = 총 e4개
E = 각 숫자에서 각 한자리씩만 바꾸니까 40개씩, e4 * 40= 4e5
- 그리고 소수인지 각각 체크해야하니까. 4e5 * sqrt(10000) = 4e7

인트 계산

INT 넘어가는수 >> 최소 횟수
근데 총 숫자가 e4개 있으니까, 이 횟수는 안넘어갈것임

코드

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

#include <iostream>
#include <queue>
#include <cmath>
 
using namespace std;
 
bool chk[10010];
bool sosuchk(int esn) {
    for(int i=2; i<= sqrt(esn); i++) {
        if(esn%i==0) return 0;
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(chk, chk+10010, 0);
        int num; cin >> num;
        int ans; cin >> ans;
        queue<int> q;
        q.push(num);
        chk[num] = 1;
        
        int cnt=0;
        bool sw = 0;
        
        while(!q.empty()) {
            int qsize = q.size();
            while(qsize--) {
                int eq = q.front(); q.pop();
                if(eq == ans) {
                    sw = 1;
                    cout << cnt << '\n';
                    break;
                }
                
                // 각 자리에서
                for(int k=0; k<4; k++) {
                    // 각 숫자를 대입
                    for(int i=0; i<10; i++) {
                        // 소수이어야하고, 체크에서 이상없어야함
                        if(k==0 && i==0) continue;
                        string es = to_string(eq);
                        es[k] = '0' + i;
                        int esn = stoi(es);
                        if(chk[esn]) continue;
                        if(sosuchk(esn)) {
                            chk[esn] = 1;
                            q.push(esn);
                        }
                    }
                }
            }
            if(sw) break;
            cnt++;
        }
        
        if(sw== 0) cout << "Impossible" << '\n';
        
        
        
    }
    return 0;
}
 
Colored by Color Scripter

cs

문제유형

BFS - 최소값

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

백준 14226 이모티콘 (0)	2021.02.06
백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 2225 합분해 쉬운 풀이 (0)	2021.02.06

백준 1309 동물원 쉬운 풀이(C++/CPP)

2021. 2. 6. 13:00

문제링크 : https://www.acmicpc.net/problem/1309

문제 접근

어떻게 해야하는지 감이 안오는데? 우선 각 케이스를 구해보자
- 2 X 0 : 0마리 1
- 2 X 1 : 0마리 1, 1마리 2
- 2 X 2 : 0마리 1, 1마리 4, 2마리 2
- 2 X 3 : 0마리 1, 1마리 6, 2마리 8, 3마리 2
다음 우리의 개수와 이전 우리의 개수의 연관관계 찾을때, 사자가 인접하지 않는다는 조건 때문에 복잡
- 첫째줄에 사자가 없는경우, 왼쪽에 있는경우, 오른쪽에 있는 경우로 나누면 어떨까 >> 케이스별 2차원 DP
- DP[N][0] = 2XN 타일 중 첫번쨰 줄에 사자 없는경우 = DP[N-1][0] + DP[N-1][1] + DP[N-1][2]
- DP[N][1] =2XN 타일 중 첫번쨰 줄의 왼쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][2]
- DP[N][2] =2XN 타일 중 첫번쨰 줄의 오른쪽에 사자 있는경우 = DP[N-1][0] + DP[N-1][1]
초기조건
- DP[0][0] = 1, DP[0][1] = 0, DP[0][2]= 0
- DP[1][0] = DP[0][0] + DP[0][1] + DP[0][2] = 1
- DP[1][1] = DP[0][0] + DP[0][2] = 1
- DP[1][2] = DP[0][0] + DP[0][1] = 1
사자가 없는 경우의수는 DP[0][0] 에 포함되며, 이후에도 계속 포함되서 계산됨

시간복잡도 계산

N칸에서 3번 계산 해줘야함, O(3*N), 3e5

인트 계산

경우의수 9901 나머지 이므로 인트 범위 가능

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
using namespace std;
 
int dp[100010][3];
int main() {
    int N; cin >> N;
    fill(&dp[0][0], &dp[100009][3], 0);
    
    dp[0][0] = 1;
    for(int j=1; j<=N; j++) {
        dp[j][0] = (dp[j-1][0] + dp[j-1][1] + dp[j-1][2]) %9901;
        dp[j][1] = (dp[j-1][0] + dp[j-1][2]) %9901;
        dp[j][2] = (dp[j-1][0] + dp[j-1][1]) %9901;
    }
    
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) %9901 << '\n';
    
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

케이스별 2차원 DP
- 각 케이스로 쪼개서 DP를 계산
- 조건이 조금 복잡하다 싶으면, 이 유형인지 한번 확인 필요

비슷한 문제

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

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

백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 2225 합분해 쉬운 풀이 (0)	2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP) (0)	2021.02.04

백준 1890 점프 쉬운 풀이(C++/CPP)

2021. 2. 6. 11:18

문제링크 : https://www.acmicpc.net/problem/1890

문제 접근

이전의 경우의 수가 다음것에 바로 사용됨 >> DP
DP
- 3이라고 적혀있는 칸일경우, 3칸 오른쪽이나 아래쪽에 값을 반영 가능할까? >> 가능할것 같음
- DP[Y][X] = Y,X칸을 갈 수 있는 경우의 수
- DP[0][0] = 1; , DP[0][0]의 값이 K일경우
- DP[K][0] += DP[0][0], DP[0][K] += DP[0][0]

시간복잡도 계산

가로 * 세로 >> O(N^2) >> 1e4

인트 계산

모두 갈수 있는 경우라면 >> 2^100 >> 1e30 >> 인트 초과 >> DP값은 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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
ll dp[110][110];
int map[110][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            cin >> map[j][i];
        }
    }
    
    fill(&dp[0][0], &dp[109][110], 0);
    dp[0][0] = 1;
    for(int j=0; j<N; j++) {
        for(int i=0; i<N; i++) {
            int k = map[j][i];
            if(k==0) continue;
            dp[j+k][i] += dp[j][i];
            dp[j][i+k] += dp[j][i];
        }
    }
    
    cout << dp[N-1][N-1]<< '\n';
    
    return 0;
}
 
Colored by Color Scripter
cs

문제유형

일반 DP

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

백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 2225 합분해 쉬운 풀이 (0)	2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP) (0)	2021.02.04

백준 2225 합분해 쉬운 풀이

2021. 2. 6. 10:38

문제링크 : https://www.acmicpc.net/problem/2225

문제 접근

감이 안오는데? 각 케이스를 생각해보자
- 20 = 19 + 1, 18+2, 17+3
- 만약 K가 3일경우엔, 20 = 18+1+1, 17+1+2, 17+2+1, ...
- 이전 값을 다시 재활용해서 사용할 수 있을것 같음 >> DP로 해보자 >> 종류 2차원 DP 문제
  - DP[K][N] = K개를 사용해서 N을 구하기 위해서 경우의 수
- 앞에는 1개로 정해놓고 뒤에만 움직이는경우
  - DP[K][N] = DP[1][0] +DP[K-1][N] + DP[1][1] + DP[K-1][N-1] + DP[1][2] + DP[1][K-2] + ...
- 근데 어짜피 K가 1이면 DP[1][K] = 1
- DP[K][N] = DP[K-1][0] + DP[K-1][1] + DP[K-1][2] + ...DP[K-1][N]
- 이때 예외가 있을까?
  - K = 1일때는 적용 안됨, 항상 종류 1
    ### 시간복잡도 계산
DP[N][K]에서 연산횟수 >> N-1번, 약 N번이라고 가정시
- O(N_K_N) = O(N^2 * K) = 8e6 >> 가능
  ### 인트 계산

dp값을 1e9 나머지로 계산해줘서 신경써줄 필요없음
### 코드

#include <iostream>
 
using namespace std;
int dp[210][210];
int main() {
    int N,K;
    cin >> N >> K;
    fill(&dp[0][0], &dp[209][210], 0);
    dp[0][0]= 1;
    // K=1 일경우 경우의수 1개 >> 각 수를 내서 만들수 있으니까
    fill(&dp[1][0], &dp[1][210], 1);
    
    for(int j=2; j<=K; j++) {
        for(int i=0; i<=N; i++) {
            for(int k=0; k<=i; k++) {
                dp[j][i] = (dp[j][i] + dp[j-1][k]) % 1000000000;
            }
            
        }
    }
    
    cout << dp[K][N] << '\n';
    
    
    return 0;
}
 

Colored by Color Scripter

문제유형

DP - 이전 종류값 만을 포함
- dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
- 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
  - 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
- 대표문제 : knapsack
  - 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
  - dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치
  - https://www.acmicpc.net/problem/12865

비슷한 문제

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

백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1520 내리막길 쉬운 풀이(C++/CPP) (0)	2021.02.04

백준 1520 내리막길 쉬운 풀이(C++/CPP)

2021. 2. 4. 19:16

문제 링크 : https://www.acmicpc.net/problem/1520

문제 접근

위에서 아래로 가는 경로가 아닌, 왼쪽이나 오른쪽으로 가는 케이스를 어떻게 해결?
- 일반적 DP로는 불가능
백트래킹?
- 시작 위치에서 끝까지 가는 모든 경로를 확인
- 한 위치에서 갈수 있는 좌표는 크게 4가지
- 그럼 최악의 케이스 4^(MN) = 4^(2500) = 2^5000 >> 시간초과 >> 불가능
끝에서부터 시작하는 DP?
- 일반적으로 DP가 연산을 줄이기 위해서 시작점부터 진행하는데
- 각 정점에서 이전에 온것을 재활용
- DP[j][i] = (j,i) 좌표까지 올수 있는 경우의 수
- DP[j][i] = min(DP[j-1][i], DP[j+1][i], DP[j][i-1], DP[j][i+1])
- 단 현재 노드보다 계단 위치 높은 케이스에서만 진행

시간복잡도 계산

O(MN) >> 2500

인트 계산

모든 입력 >> 10억 이하의정음수 >> INT 가능
dp값 : 최악의 케이스는 약 4^2500? >> 안전하게 LL 사용

코드

#include &lt;iostream&gt;
 
using namespace std;
typedef long long ll;
 
int map[510][510];
ll dp[510][510];
int N,M;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
ll dfs(int y, int x) {
    if(dp[y][x] != -1) return dp[y][x];
    
    dp[y][x] = 0;
    // 다음 노드
    for(int k=0; k&lt;4; k++) {
        int ny = y + dy[k];
        int nx = x + dx[k];
        if(ny&gt;=0 &amp;&amp; ny&lt;N &amp;&amp; nx&gt;=0 &amp;&amp; nx &lt; M) {
            // 무한루프 생각해줄필요 없음
            // 이전값과 비교해서 커야만 다음 재귀함수로 들어가기 때문에, 서로 왔다갔다 무한재귀할일은 없음
            if(map[ny][nx] &gt; map[y][x]) {
                dp[y][x] += dfs(ny, nx);
            }
        }
    }
    return dp[y][x];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&amp;map[0][0], &amp;map[509][510], 0);
    fill(&amp;dp[0][0], &amp;dp[509][510], -1);
    
    cin &gt;&gt; N &gt;&gt; M;
    for(int j=0; j&lt;N; j++) {
        for(int i=0; i&lt;M; i++) {
            cin &gt;&gt; map[j][i];
        }
    }
    
    // 시작하는 경우
    dp[0][0] = 1;
    
    cout &lt;&lt; dfs(N-1, M-1) &lt;&lt; '\n';
    
    return 0;
}
 

Colored by Color Scripter

문제유형

끝에서부터 시작하는 DP
DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
특히 2차원에서 상하좌우를 모두 고려해줘야할 때

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

백준 1744 수 묶기 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1963 소수 경로 (0)	2021.02.06
백준 1309 동물원 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 1890 점프 쉬운 풀이(C++/CPP) (0)	2021.02.06
백준 2225 합분해 쉬운 풀이 (0)	2021.02.06

PREV 1 ···6 7 8 9 NEXT

알고리즘

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

비슷한 문제

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

문제 정의

문제 접근

시간복잡도

인트 계산

대표예제 : 백준 2252 줄세우기

비슷한 유형

'알고리즘 > 개념' 카테고리의 다른 글

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

비슷한 문제

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

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

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

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

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

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

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

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

비슷한 문제

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

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

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

문제 접근

문제유형

비슷한 문제

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

문제 접근

시간복잡도 계산

인트 계산

코드

문제유형

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

티스토리툴바