[SW Expert Academy] 오랜만에 하는 코드 배틀!

그렇다고 합니다.

휴가는 필요없습니다!

코드 배틀이야 말로 진정한 피서지인 것을!

뇌가 서늘해지는 그 곳 코드배틀에서 멘붕을 겪어봅시다!

SW Expert Academy의 문제들은 외부 공개가 금지되어있기 때문에 링크로 대체합니다!!

5215. 햄버거 다이어트

어떻게 풀까?

모든 경우의 수를 확인해서 최고의 칼로리를 구하는 문제입니다!

이전에 bit를 이용해서 모든 부분집합을 구하는 경우를 올려드린적이 있습니다!

해당 문제는 이를 이용해서 햄버거와 칼로리를 모두 계산해보면 해결할 수 있습니다!

1. 모든 부분 집합을 만들어본다.

2. 칼로리가 주어진 조건보다 넘으면 무시!, 같거나 작으면 최대 만족도 갱신!

비트를 이용하여 부분집합을 만드는 법을 알고싶으시면 아래 링크를 클릭하세용!

http://sangdo913.tistory.com/entry/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9-%EB%B9%84%ED%8A%B8%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%98%EC%97%AC-%EB%AA%A8%EB%93%A0-%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9%EC%9D%84-%EA%B5%AC%ED%95%98%EC%9E%90?category=823319

코드

#pragma once
#include<cstdio>
 
int info[20][2];
 
int main() {
    int n, cal, res = 0, t;
    scanf("%d\n", &t);
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d %d\n", &n, &cal);
        res = 0;
        for(int i = 0 ;i < n; i++) {
            scanf("%d %d\n", &info[i][0], &info[i][1]);
        }
 
        for (int i = 1; i < 1 << n; i++) {
            int temp = i, idx = 0, good = 0, tcal = 0;
            while (temp) {
                if (temp & 1) {
                    good += info[idx][0];
                    tcal += info[idx][1];
                    if (tcal > cal) break;
                }
                idx++;
                temp >>= 1;
            }
            if (tcal <= cal) {
                res = res < good ? good : res;
            }
        }
        printf("#%d %d\n", tc, res);
    }
    
 
    return 0;
}

여담 

저의 코드는 부분집합을 모두 확인하기 때문에 의 시간복잡도를 가집니다.

다른 사람들이랑 비교하면 시간이 매우 느린데... 한번 확인해봐야겠습니다.

5213. 진수의 홀수 약수

어떻게 풀까?

구간 합을 이용한 문제입니다!

구간합을 위해서는 펜윅 트리나 인덱스드 트리를 이용합니다.

저같은 경우는 펜윅 트리를 이용했습니다! 사용하기 편하기 때문이죠 핫핫

약수의 개수는 어떻게 구하면 좋을까요!?

1부터 차례대로 돌면서 해당 수를 약수로 가지고 있는지 확인하면 됩니다!

이는 for문 2 개로 확인할 수 있죠!

예를 들어서, 두 수 i와 j가 있다고 합시다!

저희가 확인하려는 가장 큰 수를 n이라고 하겠습니다.

만약 i*j가 n보다 작으면,

i*j는 i라는 약수를 가지고 있다는 것이 되겠죠!

이 문제에서는 i가 홀수인 경우만 확인하기 때문에, i에 2씩 더해주면서 약수들의 합에 대한 정보를 펜윅 트리에 update를 해주고,

2 개의 수를 입력받아서 구간합을 구하면 문제가 풀리는 것입니다!

 

코드

#pragma once
#include<cstdio>
#include<cstring>
const int Size = 1000000;
long long BIT[1000001];
 
void update(int i, int to) {
    while (i <= Size) {
        BIT[i] += to;
        i += i & -i;
    }
}
 
long long get(int to) {
    long long res = 0;
    while (to > 0) {
        res += BIT[to];
        to -= to & -to;
    }
    return res;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
    for (int i = 1; i <= Size; i+=2) {
        for (int j = 1; j <= Size / i; j++) {
            update(i*j, i);
        }
    }
    for (int tc = 1; tc <= t; tc++) {
        int from, to;
        scanf("%d %d\n", &from, &to);
        printf("#%d %lld\n", tc, get(to) - get(from - 1));
    }
    return 0;
}

여담

처음에 약수를 찾는 부분이 의 시간이 걸린다고 합니다.

update()함수도의 시간이 걸리기 때문에, 

총 의 시간이 걸리겠네요!

코드 배틀 3번을 풀려고 하다가 정말 너무 어려워서 포기해버렸습니다..

그래도! 생각보다 성적은 좋게 나왔네요!

5 위!