반응형
https://www.acmicpc.net/problem/1005
1005번: ACM Craft
첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부
www.acmicpc.net
무작정 계산하는 방식으로는 시간초과로 해결할 수 없다.
DP를 사용하여 중간값들을 배열에 저장하여 해결할 수 있었다.
typedef struct {
int back[1001];
int back_num;
}NODE;
NODE MAP[1001];
int TIME[1001];
int ORDER[1001];
void input(int src, int des)
{
MAP[des].back[MAP[des].back_num++] = src;
}
int get(int W)
{
int BIGGEST = -1;
for (int i = 0; i ORDER[W])
ORDER[W] = BIGGEST;
return BIGGEST;
}
int main()
{
int T;
for (scanf("%d", &T); T>0; T--)
{
memset(&MAP, 0, sizeof(MAP));
memset(&TIME, 0, sizeof(TIME));
memset(&ORDER, 0, sizeof(ORDER));
int N, K, W;
scanf("%d %d", &N, &K);
for (int i = 1; i <= N; i++)
scanf("%d", &TIME[i]);
for (int i = 0; i
반응형