글 읽기 - 16432번 떡장수와 호랑이

sgckk 5년 전 0

단순히 모든 경우의 수를 해보며 성립할경우 바로 중지하고 정답을 출력하도록 짰습니다.

가지치기를 더 해야하나요... 상당히 당황스럽네요ㅠㅠ

#include <stdio.h>

int arr[1111][11];
int ans[1111];
int flag,n;

void bt(int t,int bf){
	int i;
	
	if(t==n+1){
		flag=1;
		return;
	}
	
	for(i=1;i<=arr[t][0];i++){
		if(arr[t][i]!=bf){
			ans[t]=arr[t][i];
			bt(t+1,arr[t][i]);
		}
		
		if(flag==1){
			return;
		}
	}
}

int main(void) {
	int j,i;
	scanf("%d",&n);
	
	for(i=1;i<=n;i++){
		scanf("%d",&arr[i][0]);
		for(j=1;j<=arr[i][0];j++){
			scanf("%d",&arr[i][j]);
		}
	}
	
	for(i=1;i<n;i++){
		if(arr[i][0]==1&&arr[i+1][0]==1){
			if(arr[i][1]==arr[i+1][1]){
				printf("-1");
				return 0;
			}
		}
	}
	
	bt(1,0);
	
	if(flag==0){
		printf("-1");
		return 0;
	}
	
	for(i=1;i<=n;i++){
		printf("%d\n",ans[i]);
	}
	
	return 0;
}

djm03178 5년 전 1

악독한 케이스를 하나 생각해봅시다. 998일 동안 매일 9종류의 떡을 다 들고 가고 마지막 2일 동안 1번 떡만 들고 가면 정답은 -1이겠죠?

그런데 매일 고를 수 있는 떡이 전날의 떡을 제외한 8종류씩이고 불가능하다는 건 1000일째가 되어야 알 수 있으니 대충 계산해 봐도 8^998 정도의 경우의 수가 있습니다. 이 수는 약 900자리의 수입니다. 감당이 될까요?

sgckk 5년 전 0

그 경우는 예외처리 해주었습니다.

대충 무슨 문제인지는 알것같은데 미리 안되는경우를 찾아서 예외처리하는거 말고 다른 방법은 없나요

djm03178 5년 전 2

visited[n번째 날][전날 m 떡을 호랑이에게 주었을 때]로 놓고 dfs를 수행하면 됩니다. 이미 방문한 상태는 재방문하지 않도록 하고요.

sgckk 5년 전 0

그렇네요 가지를 어떻게 칠까 계속 고민했는데ㅠㅠ

그냥 체크해주면 될줄 몰랐네요 바로 풀었습니다 감사합니다ㅎㅎ

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

문제

문제

출처

ICPC

16432번 떡장수와 호랑이

sgckk 5년 전 0

djm03178 5년 전 1

sgckk 5년 전 0

djm03178 5년 전 2

sgckk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말