글 읽기 - 왜틀렸을까요

minyoung403 6년 전 0

질문에 있는 웬만한 반례 다 넣어봣는데 그래도 틀렸네요..... 한 50%에서 틀립니다. 도와주세여

#include <stdio.h>
#include <iostream>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<float.h>
using namespace std;
int input1, input2,maximum;
int max1(int a, int b) {
	return (a < b) ? b : a;
}
int compare(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}
int arr[1001];
int totalhours(int input, int*hours, int*flow) {
	int i, maximum = 0;
	if (arr[input] > 0)
		return arr[input];
	for (i = 0; i < input2; i++)
		if (*(flow+i) / 10000 == input)
			break;
	maximum = hours[input - 1];
	for (int k = i; flow[k] / 10000 == input&&k<input2; k++) {
		maximum = max1(totalhours(flow[k] % 10000, hours,flow)+hours[input-1],maximum);
	}
	return arr[input]=maximum;
}
int main() {
	int i, t, p, h, k,temp1,temp2 ,result, sum,num;
	
	int testcase;
	scanf("%d", &testcase);
	while (testcase--) {
		memset(arr,0,1001);
		scanf("%d %d", &input1, &input2);
		int* hours=(int*)malloc(sizeof(int)*(input1+1));
		int* flow= (int*)malloc(sizeof(int)*(1+input2));
		maximum = 0;
		for (i = 0; i < input1; i++)
			scanf("%d", &hours[i]);
		for (i = 0; i < input2; i++) {
			scanf("%d %d", &temp1, &temp2);
			flow[i] = temp2 * 10000 + temp1;
		}
		qsort(flow, input2, sizeof(int),compare);
		scanf("%d", &num);
		printf("%d\n", totalhours(num,hours,flow));
		free(hours);
		free(flow);
	}
	return 0;
}

djm03178 6년 전 1

memset의 사용이 잘못되었습니다. memset(arr, 0, 1001); 은 1001바이트를 0으로 초기화하는 것이지, int형 1001개 (=4004바이트)를 전부 초기화해주지 않습니다. memset(arr, 0, sizeof(arr)); 이라고 하면 정답을 받습니다.

그리고 그와 별개로 이 코드는 조금 비효율적인 부분이 있는데, flow를 정렬하기는 했으나 21번째 줄에서 결국 O(input2)개를 돌아야 하기 때문입니다. 각 건물별로 인접 리스트를 따로 만들어둔다면 이렇게 할 필요가 없습니다.

djm03178 6년 전 1

그리고 건물을 짓는 데에 걸리는 시간이 0일 수도 있기 때문에, 방문 체크는 다른 방법으로 해줘야 합니다.

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜틀렸을까요

minyoung403 6년 전 0

djm03178 6년 전 1

djm03178 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말