[Algorithm] 비타알고 시즌 3 : 7월

Posted on | In

위클리 비타알고 20년 7월 1주차

보조 배터리(난이도 2)

구름 나라에는 5핀 케이블로만 충전할 수 있는 배터리, 8핀 케이블로만 충전할 수 있는 배터리, 두 케이블 모두를 사용하여 충전할 수 있는 배터리, 총 세 종류의 보조 배터리가 있다.

케이블의 종류와 각 테이블을 이용한 충전 가격이 주어졌을 때, 최대한 많은 보조 배터리를 동시에 충전할 수 있는 최소 가격을 구해보자.

입력

첫 번째 줄에는 세개의 정수 a, b, c가 공백으로 구분되어 주어진다. 세 정수는 각각 5핀 케이블로만 충전할 수 있는 보조배러티의 수, 8핀 케이블로만 충전할 수 있는 보조 배터리의 수, 두 케이블 모두 사용하여 충전할 수 있는 보조 배터리의 수를 뜻한다.

두 번째 줄에는 판매중인 케이블의 수 n이 주어진다.

이 후 한 줄에 하나씩 케이블의 정보가 ci, ti 의 형태로 주어진다. 이는 i번째 케이블의 가격이 ci이고, ti==0인 경우 5핀 테이블, ti==1인 경우 8핀 케이블을 뜻한다.

출력

최대한 많은 보조 배터리를 동시에 충전하고자 할 때, 사야 하는 케이블의 최소 가격을 출력한다.

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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int main(){
    int a, b, c;
    int n;
    int cnt = 0, res = 0;
    
    pair<int, int> p;
    vector<pair<int, int>> price;
    
    cin >> a >> b >> c;
    cin >> n;
    
    for(int i=1; i<=n; i++){
        cin >> p.first >> p.second;
        price.push_back(p);
    }
    
    sort(price.begin(), price.end(), less<>());
        
    while(a+b+c != 0){
        p = price[0];
        if(p.second==0){ //5핀 - a
            if(a>0){
                a--;
                cnt++;
                res += p.first;
            }else if (c>0){
                c--;
                cnt++;
                res += p.first;
            }else{
                cout << "a도 c도 없는 상황 " << endl;
            }
        }else{ //8핀 - c
            if(b>0){
                b--;
                cnt++;
                res += p.first;
            }else if(c>0){
                c--;
                cnt++;
                res += p.first;
            }else{
                cout << "b도 c도 없는 상황" << endl;
            }
        }
        price.erase(price.begin());
    }
    
    cout << cnt << " " << res << endl;
}

위클리 비타알고 20년 7월 2주차

곱셈놀이 (난이도 2)

홍현이는 얼마 전 큰 수의 곱셈을 배운 사촌 동생과 게임을 하고자 한다.

어떤 수 n이 주어졌을 때, 2와 3, 곱하기 기호만으로 숫자 m을 만들기 위해 최소 몇번의 연산이 필요한지 구하는 게임이다.

홍현이의 사촌 동생이 답을 말하면 그 답이 맞는지 빠르게 확인할 수 있도록 답을 구해주는 프로그램을 작성해보자!

입력

두 수 n, m이 공백으로 구분되어 주어진다.

출력

n을 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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int n, m;
    int cnt = 0;
    int flag1 = 0, flag2 = 0;
    
    scanf("%d %d", &n, &m);
    
    if(m%n != 0){
        printf("-1\n");
    }else{
        int tmp = m/n;
        while(tmp != 1){
            if(tmp%2 != 0 && tmp%3 != 0){
                if(tmp != 1){
                    cnt = -1;
                }
                break;
            }
            if(tmp%2 == 0){
                tmp = tmp/2;
                cnt++;
            }
            if(tmp%3 == 0){
                tmp = tmp/3;
                cnt++;
            }
        }
        printf("%d\n", cnt);
    }
    
}

이렇게 풀었는데 테스트 케이스에서 틀린 답이 있었다. (왜인지는 모름.. 예시 케이스도 알려주셔야 하는거 아닌가요 ㅇㅅㅠ)