글 읽기 - 반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

연결리스트 방식으로 코드를 짰습니다. 아래 표는 의상 종류를 늘릴 때, 의상 수를 추가하는 형태입니다. 즉, 첫 줄에 의상 종류가 1이고 의상 수가 3이었는데 두 번째 줄에 의상 종류가 2이고 의상 수가 5 이면 의상 수가 3인 종류 하나와 의상 수가 2인 종류 하나가 있는 형태라 생각해주시면 되겠습니다. 표는 총 가짓수를 구하는 공식을 나타내는 겁니다.

코드에서 사용한 방식은 표에서 나오는 방식을 그대로 적용한 것입니다.

(수정)n이 0인 경우를 추가하였습니다. typedef 구문을 삭제하였습니다.)

누적 의상 수	의상 종류	총 가짓수
5	1	5
7	2	5 + 5 * 2 + 2 = 17
10	3	17 + 17 * 3 + 3 = 71

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Cloth {
	char gear[25], part[25];
	struct Cloth *next;
};
int main(void)
{
	int T, n, i, j, k, *num, count = 0;
	unsigned long long int *sum;
	char gear[30], part[30];
	struct Cloth *node, *now, *tmp;
	scanf("%d", &T);
	sum = (unsigned long long int *)calloc(T, sizeof(unsigned long long int));
	for (i = 0; i < T; i++)
	{
		scanf("%d", &n);
		if (n == 0)
		{
			printf("%lldu\n", sum[i]);
			continue;
		}
		now = (struct Cloth *)calloc(n, sizeof(struct Cloth));
		num = (int *)calloc(n, sizeof(int));
		for (j = 0; j < n; j++)
		{
			scanf("%s %s", gear, part);
			tmp = now;
			for (k = 0; k < j; k++)
			{
				if (strcmp(now[k].part, part) == 0)
				{
					for (tmp = &now[k]; tmp->next != NULL; tmp = tmp->next);
					break;
				}
				else
					tmp = &now[k + 1];
			}
			node = (struct Cloth *)calloc(1, sizeof(struct Cloth));
			strcpy(node->gear, gear);
			strcpy(node->part, part);
			if (tmp == &now[k] && strcmp(tmp->gear, "") == 0)
				memcpy(tmp, node, sizeof(struct Cloth));
			else
				tmp->next = node;
		}
		for (j = 0; j < n; j++)
		{
			if (strcmp(now[j].gear, "") == 0)
				break;
			else
				count++;
			for (tmp = &now[j]; tmp != NULL; tmp = tmp->next)
				num[j]++;
		}
		for (j = 0; j < count; j++)
			sum[i] = sum[i] + sum[i] * num[j] + num[j];
		count = 0;		
	}
	for(i=0;i<T;i++)
		printf("%lld\n", sum[i]);
	return 0;
}

adfsfsf 5년 전 0

해결했습니다. 의상 종류가 3개 이상일 때 안 되더군요. 그 점을 해결했더니 통과되었습니다.

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

문제

문제

출처

ICPC

반례를 찾지 못 하겠습니다.

adfsfsf 5년 전 0

adfsfsf 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말