글 읽기 - 어느 부분에서 틀렸을까요?

hongjg3229 3년 전 0

한 23%에서 틀립니다.

방법은 길이를 긴 순서대로 먼저 고정해놓고 dp를 돌려서 해당 길이에서 가능한 숫자가 있는지 먼저 탐색하고,

만약 만들 수 있는 숫자가 있다면 dp를 역추적하면서 가장 큰 숫자를 만들어서 출력합니다.

역추적에서 숫자를 만들 때 우선적으로 9~1까지의 숫자를 뒤에 붙이는 게 가능한가 보고, 안된다면 그 다음은 11을 붙이는게 가능한가 보고, 그 다음은 0을 붙이는게 가능한가 봐서, 가능한 앞 자리 숫자가 크게 만듭니다.

방법이 틀렸는지, 구현을 실수했는지.. 한참 생각해봐도 어디서 틀렸는지 모르겠습니다.

틀린 부분이나 반례를 찾아주실 분이 계실까요..?

#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()

int n, m;
char cache[10][10][110000];
ll toint(string s) {
	ll ret = 0;
	for (int i = 0; i < s.size(); i++) {
		ret *= 10;
		ret += s[i] - '0';
	}
	return ret;
}

int dp(int cnt, int n11, ll mod) {
	if (cnt == n) {
		if (mod == 0 && n11 == 0) return 1;
		else return 0;
	}
	if (n11 < 0) return 0;

	char& ret = cache[cnt][n11][mod];
	if (ret != -1) return ret;

	ret = 0;
	for (int i = 0; i < 10; i++) {
		ret |= dp(cnt + 1, n11, (i + mod * 10) % m);
	}
	ret |= dp(cnt + 1, n11 - 1, (11 + mod * 100) % m);
	return ret;
}

string ans;
void trace(int cnt, int n11, ll mod) {
	if (cnt == n) {
		cout << toint(ans) << '\n';
		return;
	}

	for (int i = 9; i >= 1; i--) {
		if (dp(cnt + 1, n11, (i + mod * 10) % m)) {
			ans += to_string(i);
			trace(cnt + 1, n11, (i + mod * 10) % m);
			return;
		}
	}
	if (dp(cnt + 1, n11 - 1, (11 + mod * 100) % m)) {
		ans += "11";
		trace(cnt + 1, n11 - 1, (11 + mod * 100) % m);
	}
	else if (dp(cnt + 1, n11, mod * 10 % m)) {
		ans += "0";
		trace(cnt + 1, n11, mod * 10 % m);
	}
}

void solve(int tc) {
	cin >> n >> m;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= m; k++)
				cache[i][j][k] = -1;

	for (int i = n; i >= 0; i--) {
		if (dp(0, i, 0)) {
			ans = "";
			trace(0, i, 0);
			break;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	if (1) {
		int T; cin >> T;
		for (int i = 1; i <= T; i++) solve(i);
	}
	else {
		solve(0);
	}
	return 0;
}

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

문제

문제

출처

ICPC

어느 부분에서 틀렸을까요?

hongjg3229 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말