글 읽기 - 61%에서 runtime error가 뜹니다..! (dfs사용)

kjh31021 1년 전 0

DP를 사용해야하는 문제라고 들었는데, DP가 뭔지 잘 모르겠어서 다음과 같은 알고리즘으로 짜보았습니다.

자꾸 61%에서 런타임에러가 떠서 51번째 조건문을 추가하여 시간을 최대한 단축했는데도 똑같이 61%에서 런타임에러가 뜹니다.

DP 사용하지 않고 아래와 같은 dfs(?) 방식으로 해결하되 시간을 더 줄이는 방법은 없을까요?

#include <stdio.h>
#include <stdlib.h>

int count[15];		// 그림을 사지 않은 i번째 예술가는 0, 한번이라도 산 i번째 예술가는 1 
int price[15][15];	// 각 경우에 따라 그림을 살 때의 가격이 저장되는 배열 
int now_price[15];	// i번째에 그림을 거래한 가격이 저장되는 배열 
//int path[15];		// i번째에 그림을 거래한 사람이 누구인지 저장되는 배열 
int max_number;		// 그림을 소유 했던 사람들의 최댓값 
int num;			// 현재 그림을 소유한 사람이 몇 명인지 저장하는 변수 (1 작게 입력됨) 
int n;				// 총 예술가의 수

void buy(int now_person);

int main(void) {
	// 예술가의 수 n이 입력되고, price[][] 이중배열이 입력된다. 
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%1d", &price[i][j]);
	
	// 0번 예술가가 그림을 가지고 있으니 count[0]=1 
	count[0] = 1;
	// 0번째 거래한 사람은 0번 예술가 
	//path[0] = 0;
	// 현재 그림을 소유한 사람은 1명(1작게 입력되니까 0 대입) 
	num = 0;
	
	// 현재 0번 예술가가 그림을 가지고 있는 것을 시작으로 함수를 돌린다. 
	buy(0);
	
	
	printf("%d", max_number+1);
	
	return 0;
}

void buy(int now_person) {
	for(int i=0;i<n;i++) {
		if(now_person == i || count[i] == 1)
			continue;
		
		if(now_price[num] <= price[now_person][i]) {
			count[i] = 1;
			now_price[++num] = price[now_person][i];
			//path[num] = i;
			
			if(max_number < num)
				max_number = num;
				
			// 만약 max_number가 이미 최대 인원 수라면 출력 후 프로그램을 종료한다 (시간 문제) 
			if(max_number == n-1) {
				printf("%d", n);
				exit(0);
			}
			else
				buy(i);
			
			count[i] = 0;
			now_price[num--] = 0;
			//path[num--] = 0;
		}
	}
	
	return;
}

keroro729 5달 전 0

n이 15밖에 안돼서 저도 dfs로 접근했다가 메모리초과, 시간초과가 떠서 이해가 안되었었는데

그래프가 모든 노드가 서로 연결되어 있는 그래프라

n이 15만 되어도 탐색 경우의 수 가 15! (1,307,674,368,000)입니다.

dfs로는 효율적으로 해결할 수 없는 문제였네요.

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

문제

문제

출처

ICPC

61%에서 runtime error가 뜹니다..! (dfs사용)

kjh31021 1년 전 0

keroro729 5달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말