문제링크 : 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;
}
 
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

문제링크 : 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;
}
 
 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

문제링크 : 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;
}
 
 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

+ Recent posts

티스토리툴바