글 읽기 - 1700번 어떤경우에서 틀린지 모르겠습니다

penipeni 7년 전 0

그리디 알고리즘 문제입니다.

답을 도출하는 방법이나 그런건 맞는거같은데 특정 테스트케이스를 통과하지 못하는것 같은데,

어떤경우인지 도저히 모르겠네요

기본 테스트케이스와 제가 만든 몇개의 테스트케이스는 통과합니다.

이하는 제가 푼 방법입니다...

이미꽃혀있는 콘센트라면 그냥 skip해버리고, 가장 최근에 나올 중복된 콘센트 n-1개를 놔두고 나머지를 갈아끼우는걸 매 시행 반복하는 방법으로 풀었습니다

예를들어..

3 7

1 2 3 5 1 2 1 의 경우 첫 시행에서

1 2 3 5 1 2 1 굵은 표시와 같이 최근에 나온 1 2 를 남기고 3을뽑고 5를갈아끼웁니다

그리고 이방법을 끝날때까지 반복합니다.

#include <stdio.h>
#include <malloc.h>

int main(void) {
	int i, j, k, l;
	int conSu, su, *arr, dap;
	int *conArr, *conArrFlag, flag;

	scanf("%d %d", &conSu, &su);
	arr = (int*)malloc(sizeof(int)*su);
	for (i = 0; i < su; i++)
		scanf("%d", &arr[i]);
	
	conArr = (int*)malloc(sizeof(int)*conSu);
	conArrFlag = (int*)malloc(sizeof(int)*conSu);

	for (i = 0; i < conSu; i++) {
		conArr[i] = arr[i];
	}

	i = conSu;
	dap = 0;
	while (i < su) {
		int flag=0;
		for (j = 0; j < conSu; j++) {
			if (arr[i] == conArr[j]) {
				flag = 1;
			}
		}
		if (flag == 1) {
			i++;			
			continue;
		}
		
		for (j = 0; j < conSu; j++) 
			conArrFlag[j] = 0;

		for (j = i; j < su; j++) {
			for (k = 0; k < conSu; k++) {
				if (arr[j] == conArr[k]) {
					conArrFlag[k] += 1;
					break;
				}
			}
			flag = 0;
			for (k = 0; k < conSu; k++) {
				if (conArrFlag[k] == 0)
					flag++;
			}
			if (flag == 1) 
				break;
		}
		for (j = 0; j < conSu; j++) {
			if (conArrFlag[j] == 0) {
				conArr[j] = arr[i];
				dap++;
				break;
			}
		}
		i++;
	}
	printf("%d", dap);
}

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

문제

문제

출처

ICPC

1700번 어떤경우에서 틀린지 모르겠습니다

penipeni 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말