[PS]USACO Dec 2006 Bronze

시작하기 전에...

오늘은 무슨 문제를 풀어야 할까 또 고민하며 백준 문제집을 기웃거리고 있었다. 그렇지만 아무리봐도 내 수준에 맞는 재밌는 문제집이 없는 것 같아 실망하고 있던 찰나, 대회 문제들을 한 번 풀어보는 건 어떨까 하는 생각이 들었다. 그렇게 찾은 대회가 USACO였고, 그 중에 그나마 쉬워보이는 Bronze 문제 3개를 풀어보았다.

6210: Wonderprime Brands

6210번: Wonderprime Brands
신기한 문제였다. 3문제 중에 제일 어려워보여서 마지막에 풀었는데, 예상치 못한 곳에서 꽤 많은 시간이 걸렸다. 처음에 완전탐색으로 짰으나, 정답에 상한이 없어서 적당한 탐색의 초기값을 설정해주지 않으면 시간 초과가 났기 때문이다.

#include <iostream>
#include <cmath>
using namespace std;

typedef long long int lli;

int d;
lli n;

bool isPrime(lli num)
{
    lli sq = sqrt(num/1.0);
    for(lli i=2; i<=sq; i++)
        if(num%i==0) return false;
    return true;
}

bool isWonderPrime(lli num)
{
    for(int i=d; ; i++)
    {
        lli mod = pow(10, i);
        lli a = num / mod;
        lli b = num % mod;
        if(a*10<pow(10,d)) break;
        if(b*10<mod) continue;
        if(isPrime(a) && isPrime(b)) return true;
    }
    return false;
}

int main()
{
    // 입력 받기
    cin >> d >> n;
    // solve
    lli ans = -1;
    if(n<(pow(10, 2*d-1)+pow(10, d-1))) n = pow(10, 2*d-1)+pow(10, d-1);
    for(lli i=n; ; i++){
        if(isWonderPrime(i))
        {
            ans = i;
            break;
        }
    }
    // 결과 출력
    cout << ans << '\n';
    return 0;
}

위 코드에서

if(n<(pow(10, 2*d-1)+pow(10, d-1))) n = pow(10, 2*d-1)+pow(10, d-1);

이 부분이 시간 초과를 해결하는 데 필요한 코드였다.

6211: The Eating Puzzle

6211번: The Eating Puzzle
간단한 Brute Force 문제였다. 다만 조합 탐색을 살짝 섞어주어서 간단하게 풀 수 있었다.

#include <iostream>
#include <vector>
using namespace std;

int c, b;
int input[22];
vector<int> vc;

int search(int i, int sum)
{
    if(i==b) return sum;
    if(sum+input[i] > c) 
        return search(i+1, sum);
    else
    {
        int a = search(i+1, sum);
        vc.push_back(input[i]);
        int b = search(i+1, sum+input[i]);
        return max(a, b);
    }
}

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    // 입력 받기
    cin >> c >> b;
    for(int i=0; i<b; i++)
        cin >> input[i];
    // solve (brute force)
    int ans = search(0, 0);
    // 결과 출력
    cout << ans << '\n';
    return 0;
}

6212: Dream Counting

6212번: Dream Counting
3문제 중 제일 간단한 문제였다. 뭔가 수학적으로 풀면 훨씬 빠른 시간복잡도로 풀 수 있을 것 같았지만 일단 풀리는 대로 풀어보았다.

#include <iostream>
#include <vector>
using namespace std;

int n, m;
long long int input[500001];
int digit[11];

void count(int i)
{
    while(i)
    {
        digit[i%10]++;
        i = i/10;
    }
    return;
}

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    // 입력 받기
    cin >> m >> n;
    // solve (brute force)
    for(int i=m; i<=n; i++)
        count(i);
    // 결과 출력
    int ret = 0;
    for(int i=0; i<10; i++)
        cout << digit[i] << " ";
    cout << '\n';
    return 0;
}

정리

대회 문제가 예제 문제들에 비해서 약간 까다로운 감은 있는 것 같다. 내가 competitive programming을 준비하는 건 아니지만 재미를 위해서는 앞으로도 대회문제를 푸는 게 좋을 것 같다. 다만 Bronze는 생각보다 쉽게 느껴졌기에 좀 더 난이도 높은 대회 문제를 준비해야겠다.