2024-02-26

 

-로프(2217, Baekjoon)

간단한 그리디 문제였다. n개의 로프를 사용하여 가장 높은 무게를 들려면, 자신보다 들 수 있는 중량이 큰 로프의 수 곱하기 자신이 들 수 있는 중량의 크기가 가장 큰 로프를 고르면된다. 정렬을 이용하여 간단히 풀었다.

<소스코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n;
vector <int> vec;

int main()
{
    int i, ans = -2e9;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        int x;
        scanf("%d", &x);
        vec.push_back(x);
    }
    sort(vec.begin(), vec.end());
    for(i=0;i<n;i++) {
        ans = max(ans, (n - i) * vec[i]);
    }
    printf("%d", ans);
    return 0;
}

-주식(11501, Baekjoon)

뒤에서부터 탐색을 해야하는 문제이다. 처음에 앞에서부터 탐색을 하는바람에 한참 해맸었다. 마찬가지로 간단한 그리디 알고리즘이다. 뒤에서부터 검사하며, 최댓값을 갱신해가며, 아니라면 판매하는 식으로 처리를 해주면 된다. 문제에서 64bit 정수형으로 표현하라 하였음으로, int가 출력자료형이 되어선 안된다.

<소스코드>

#include <stdio.h>
#include <vector>

using namespace std;

int main()
{
    int i, j;
    int t;
    scanf("%d", &t);
    while(t--) {
        int n;
        vector <int> vec;
        scanf("%d", &n);
        for(i=0;i<n;i++) {
            int x;
            scanf("%d", &x);
            vec.push_back(x);
        }
        unsigned long long ans = 0;
        int mx = -1;
        for(i=n-1;i>=0;i--) {
            if(vec[i] < mx) {
                ans += (mx - vec[i]);
            }
            else {
                mx = vec[i];
            }
        }
        printf("%llu\n", ans);
        vec.clear();
    }
    return 0;
}

-베르트랑 공준(4948, Baekjoon)

n과 2n사이에있는 소수의 개수를 구하는 문제이다. 에라토스테네스의 체를 사용하여, n~ n*2까지의 소수를 구하는 간단한 문제였다.

<소스코드>

#include <stdio.h>

int prime[250000];

void IsPrime()
{
    int i, j;
    prime[1] = 1;
    for(i=2;i<250000;i++) {
        if(prime[i] == 1) continue;
        for(j=i*2;j<250000;j+=i) {
            prime[j] = 1;
        }
    }
    return;
}

int main()
{
    int i;
    IsPrime();
    while(1) {
        int x;
        scanf("%d", &x);
        if(x == 0) break;
        int res = 0;
        for(i=x + 1;i<=x*2;i++) {
            if(prime[i] == 0) res++;
        }
        printf("%d\n", res);
    }
    return 0;
}

-30(10610, Baekjoon)

3의 배수 판정법을 알면 쉽게 풀린다. 먼저 10으로 나누어떨어져야함으로, 0이 주어진 수배열에 없다면, 30의 배수가 불가능함으로, -1을 출력해준다. 또한 0을 제외한 나머지 각 자리숫자의 합이 3의 배수가아닐시에도 -1을 출력해준다. 만약 두 조건 모두 아니라면, 30의 배수가 가능한 배열임으로, 가장큰 수 를 구하기위해, 배열을 오름차순 정렬한 후 출력하면 된다. 3의 배수판정법을 모른다면 막막할 수 있는 문제라고 생각한다.

<소스코드>

#include <string.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

char s[100010];
int arr[100010];

int main()
{
    int i, j;
    scanf("%s", s);
    int l = strlen(s);
    int idx = -1;
    for(i=0;i<l;i++) {
        if(s[i] == '0') {
            idx = i;
        }
        arr[i] = s[i] - '0';
    }
    if(idx == -1) {
        printf("-1");
        return 0;
    }
    int sum = 0;
    for(i=0;i<l;i++) sum += arr[i];
    if(sum %3 == 0) {
        sort(arr, arr+l);
        reverse(arr, arr+l);
        for(i=0;i<l;i++) printf("%d", arr[i]);
    }
    else printf("-1");
    return 0;
}