그냥 간단한 DP문제.
m이 먼저나왔으면 좋았을텐데, 동전을 다 받은다음 나온다.
dp 테이블 크기가 작고 귀찮아서 대충 풀었는데, 시간복잡도를 고려하면 배열을 선언해서 동전을 저장한 다음, m을 받고 난 뒤, dp테이블을 m까지 계산하는게 빠르다.
#include <stdio.h>
int main() {
int T;
scanf("%d", &T);
while (T--) {
int dp[10010] = { 1 };
int n, c, m;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &c);
for (int i = 0; i <= 10000 - c; i++) {
if (dp[i]) {
dp[i + c] += dp[i];
}
}
}
scanf("%d", &m);
printf("%d\n", dp[m]);
}
return 0;
}
풀긴 풀었는데, 솔직히 테스트케이스가 부실해서 통과한거 같다.
대회에서 사용했던 I/O(http://acmacpc.org/archive/y2013/)로 테스트해보면 간당간당한게 몇 개 있다. 내 컴퓨터에서 약 2~3초 정도 걸리는데, BOJ서버에선 3초를 넘길 거 같다.
나의 경우엔 백트래킹으로 풀었다.
계속 타임리밋이 뜨길래 메모이제이션에 inline까지 써가면서 처절하게 풀었는데 효과가 없었다. 디버깅을 해보니 함수콜에 오버헤드가 큰 것이 원인이였다.
(inline인데 왜 오버헤드가 큰걸까… 예전에 C++배울땐 매크로함수랑 똑같은 기능이라 배운것 같은데…)
그래서 최대한 함수콜을 줄이기 위해 내림차순으로 정렬한 뒤 백트래킹을 진행했다.
이렇게하면 if (dmg + remain_dmg < hp) return;과 연계되어 함수콜이 많이 줄어든다.
나름 많이 헤맨거 같은데 모로가도 서울만 가면 된다고, 메모리 & 시간으로 1등먹어서 기분 좋다.
#include <stdio.h>
long long stat[5][3] = { 0 };
long long memo[1002][5][2] = { 0 };
long long T, hp;
long long minCost, minDmg;
long long pow(long long val, int k) {
long long result = 1;
for (int i = 0; i < k; i++) {
result *= val;
}
return result;
}
inline void backtracking(int charCode, long long dmg, long long cost, long long remain_dmg) {
long long _cost, _dmg;
if (dmg + remain_dmg < hp)
return;
for (int i = 0; i <= stat[charCode][0]; i++) {
_cost = cost + memo[i][charCode][1];
_dmg = dmg + memo[i][charCode][0];
if (_cost > minCost)
return;
if (_dmg >= hp) {
if (minCost >= _cost) {
if (minCost != _cost || minDmg >= _dmg)
minDmg = _dmg;
minCost = _cost;
}
return;
}
if (charCode < 4) {
backtracking(charCode + 1, _dmg, _cost, remain_dmg - memo[stat[charCode][0]][charCode][0]);
}
}
}
int main() {
scanf("%lld", &T);
while (T--) {
long long maxDmg = 0, maxCost = 0;
minCost = pow(10, 12) * 5;
minDmg = pow(10, 12) * 5;
scanf("%lld", &hp);
for (int i = 0; i < 5; i++) {
scanf("%lld %lld %lld", &stat[i][0], &stat[i][1], &stat[i][2]);
maxDmg += stat[i][0] * stat[i][1];
maxCost += stat[i][0] * stat[i][2];
}
if (maxDmg <= hp) {
if (maxDmg == hp) {
printf("%lld %lld\n", maxCost, maxDmg);
}
else {
printf("We are doomed!!\n");
}
}
else {
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 5; j++) {
if (stat[i][0] < stat[j][0]) {
stat[i][0] ^= stat[j][0] ^= stat[i][0] ^= stat[j][0];
stat[i][1] ^= stat[j][1] ^= stat[i][1] ^= stat[j][1];
stat[i][2] ^= stat[j][2] ^= stat[i][2] ^= stat[j][2];
}
}
}
for (int i = 0; i < 5; i++) {
for (int j = 0; j <= stat[i][0]; j++) {
memo[j][i][0] = stat[i][1] * j;
memo[j][i][1] = stat[i][2] * j;
}
}
backtracking(0, 0, 0, maxDmg);
printf("%lld %lld\n", minCost, minDmg);
}
}
}
#include <stdio.h>
int main() {
int T;
int n;
scanf("%d", &T);
while (T--) {
int timeline[1010] = { 0 };
int a, b, max = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("\n%*c %d %d", &a, &b);
max = max > b ? max : b;
for (; a < b; a++)
timeline[a]++;
}
for (int i = 0; i < max; i++)
timeline[i] > 0 ? printf("%c", 'A' + timeline[i] - 1) : NULL;
printf("\n");
}
return 0;
}