글 읽기 - 틀렸습니다만 이틀째입니다..

jungby1 4년 전 0

dp 배열을 chosen이랑 remain으로 돌리니깐 중복되는게 합쳐져서 chosen이랑 left 변수로 짯습니다. 논리구조도 괜찮은거 같고, 테스트 케이스도 잘 되는데 어디서 제가

또 뭘 빼먹었는지.... 제가 생각할 수 있는 건 다 고쳤는데 계속 틀렸다고 뜨니깐 답답하네요.. 고수님들의 구제가 절실히 필요합니다.

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;

int n,k, mod[16], len[16];
long long dp[1<<16][16];
char num[15][51];

int find_remain(char num[], int k){
	int ret=0;
	for(int i=0; i<strlen(num); i++){
		ret= (ret*10+(num[i]-'0'))%k;
	}
	return ret; 
}

long long correct(int chosen, int remain, int left){
	
	if(chosen==(1<<n)-1){
		if(remain==0) return 1;
        else if(remain!=0) return 0;
	}
	long long &ret = dp[chosen][left];
	if(ret!=-1) return ret;
	
	ret=0;
	for(int i=0; i<n; i++){
		if((chosen&(1<<i))==0){
			ret += correct(chosen|(1<<i), (int)(remain*pow(10,len[i])+mod[i]) % k, left-1);
		}
	}
	return ret;
}

long long gcd(long long a, long long b){
	while(b!=0){
		long long r=a%b;
		a=b;
		b=r;
	}
	return a;
}

int main() {
	
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	long long top,bot=1;
	memset(dp, -1, sizeof(dp)); 
	cin >> n;
	for(int i=1; i<=n; i++) bot *= i;
	for(int i=0; i<n; i++) {
		cin >> num[i]; 
		len[i]= strlen(num[i]);
	}
	cin >> k;
	for(int i=0; i<n; i++){
		mod[i]= find_remain(num[i],k); 
	}
	top= correct(0,0,n);
	long long divide =gcd(top, bot);
	if(top!=0) cout << top/divide <<"/" << bot/divide ;
	else if(top==0) cout << "0/1";
	return 0;
}

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

문제

문제

출처

ICPC

틀렸습니다만 이틀째입니다..

jungby1 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말