Codeforces Round #381 (Div. 2)

Codeforces Round #381 (Div. 2): http://codeforces.com/contest/740

예전에 풀었던 코포셋인데.. 오늘 뜬금없이 코포 들락날락하다가 A번을 9번이나 틀렸길래 한번 잡아봤다.

근데 오늘 더 틀린듯 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

와.. 이 문제는 정말 악마의 문제다.

스탠딩 봐도 한번에 맞춘사람이 정말 드물고.. 터진사람도 엄청 많다.

다른 문제도 중요하지만, 제발 이런거 시스템에서 나가지 말라고 남겨본다.

A. Alyona and copybooks

이 망할인간이 copybook이 이미 n권있는데 k권을 더해서 n+k가 4로 나눠떨어지게 갖는다고 한다.

1권을 사면 a원이 들고 2권을 사면 b원이 들고 3권을 사면 c원이 든다고 할 때,

n+k가 4로 나눠떨어지도록 k권을 사는 가장 저렴한 금액은 얼마인지 출력하는 문제이다.

가히 역대급 낚시킹 문제가 아닌가 싶다.

일단 n이 5라고 하면 보통 3권만 더 맞추면 4로 나눠떨어지기 때문에 3을 만드는 가장 저렴한 금액이 얼마인지 찾을 것이다.

당연히 3을 만드는 방법은 [1,2], [1,1,1], [3] 이렇게 3가지 방법이 있는데,

이와 유사한 문제를 많이 풀어본 나로써는 항상 이렇게 코딩을 할 것이다.

d[x] = min({f(x-1)+a, f(x-2)+b, f(x-3)+c});

이렇게 코딩하면 생각할 것도 없고 실수할 일도 없다.

코포나 각종 콘테를 돌면서 점점 느끼는건... 내가 생각하지 않을수록 정답을 맞을 확률이 높아진다는 것이다.

문제를 구하는 거는 전적으로 컴퓨터에게 맡기자.

그런데 함정이 있다. 위의 식이 d[x]를 f(x)라는 함수를 호출해서 채워넣는 식인데, 여기서 x라는 값을 1~3 사이의 값만 넣어주면 안된다.

그러니까 n+k가 4의 배수가 되는 방법은 k가 3보다 큰 수가 되었을 때도 성립한다는 것이다.

그래서 아래와 같이 코딩해야 한다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
ll d[20];
int n,a,b,c;
ll f(int x) {
    if(x%4==0) return 0;
    else if(x<0) return inf;
    ll &ret = d[x];
    if(ret) return ret;
    else ret = inf;
    return ret = min({f(x-1)+a, f(x-2)+b, f(x-3)+c});
}
int main() {
    scanf("%d%d%d%d",&n,&a,&b,&c);
    if(n%4==0) return 0&puts("0");
    n=12-n%4;
    printf("%lld\n", f(n));
    return 0;
}

여기서도 또 주의해야 할 점이 있는데, 반드시 dp 테이블을 long long으로 선언해야 한다는 것이다.

inf로 10억이 넘는 값을 줬기 때문에 a,b,c가 2번이상 더해짐으로써 범위가 터질 수 있다.

그러니까 14번째줄 같은 dp식을 세울 때에는 그냥 생각하지 말고 long long 쓰자. ㅠㅜ

이 문제 엄청 틀렸다.

무슨 A번 문제를 이렇게 틀리냐... ㄷㄷ