글 읽기 - 도움이 절실합니다...

djs100201 3년 전 2

정말 틀린점을 모르겠습니다...

아래 케이스는 2~100까지 숫자를 넣었을 때 결과입니다.

1 1
7 7
4 11
2 71
6 111
8 711
10 1111
18 7111
22 11111
20 71111
28 111111
68 711111
88 1111111
108 7111111
188 11111111
200 71111111
208 111111111
288 711111111
688 1111111111
888 7111111111
1088 11111111111
1888 71111111111
2008 111111111111
2088 711111111111
2888 1111111111111
6888 7111111111111
8888 11111111111111
10888 71111111111111
18888 111111111111111
20088 711111111111111
20888 1111111111111111
28888 7111111111111111
68888 11111111111111111
88888 71111111111111111
108888 111111111111111111
188888 711111111111111111
200888 1111111111111111111
208888 7111111111111111111
288888 11111111111111111111
688888 71111111111111111111
888888 111111111111111111111
1088888 711111111111111111111
1888888 1111111111111111111111
2008888 7111111111111111111111
2088888 11111111111111111111111
2888888 71111111111111111111111
6888888 111111111111111111111111
8888888 711111111111111111111111
10888888 1111111111111111111111111
18888888 7111111111111111111111111
20088888 11111111111111111111111111
20888888 71111111111111111111111111
28888888 111111111111111111111111111
68888888 711111111111111111111111111
88888888 1111111111111111111111111111
108888888 7111111111111111111111111111
188888888 11111111111111111111111111111
200888888 71111111111111111111111111111
208888888 111111111111111111111111111111
288888888 711111111111111111111111111111
688888888 1111111111111111111111111111111
888888888 7111111111111111111111111111111
1088888888 11111111111111111111111111111111
1888888888 71111111111111111111111111111111
2008888888 111111111111111111111111111111111
2088888888 711111111111111111111111111111111
2888888888 1111111111111111111111111111111111
6888888888 7111111111111111111111111111111111
8888888888 11111111111111111111111111111111111
10888888888 71111111111111111111111111111111111
18888888888 111111111111111111111111111111111111
20088888888 711111111111111111111111111111111111
20888888888 1111111111111111111111111111111111111
28888888888 7111111111111111111111111111111111111
68888888888 11111111111111111111111111111111111111
88888888888 71111111111111111111111111111111111111
108888888888 111111111111111111111111111111111111111
188888888888 711111111111111111111111111111111111111
200888888888 1111111111111111111111111111111111111111
208888888888 7111111111111111111111111111111111111111
288888888888 11111111111111111111111111111111111111111
688888888888 71111111111111111111111111111111111111111
888888888888 111111111111111111111111111111111111111111
1088888888888 711111111111111111111111111111111111111111
1888888888888 1111111111111111111111111111111111111111111
2008888888888 7111111111111111111111111111111111111111111
2088888888888 11111111111111111111111111111111111111111111
2888888888888 71111111111111111111111111111111111111111111
6888888888888 111111111111111111111111111111111111111111111
8888888888888 711111111111111111111111111111111111111111111
10888888888888 1111111111111111111111111111111111111111111111
18888888888888 7111111111111111111111111111111111111111111111
20088888888888 11111111111111111111111111111111111111111111111
20888888888888 71111111111111111111111111111111111111111111111
28888888888888 111111111111111111111111111111111111111111111111
68888888888888 711111111111111111111111111111111111111111111111
88888888888888 1111111111111111111111111111111111111111111111111
108888888888888 7111111111111111111111111111111111111111111111111
188888888888888 11111111111111111111111111111111111111111111111111

제가 정답 코드로 돌려본 정답과 일치하는 것 같은데 어디서 틀렸을지 감이 안잡힙니다...

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;
int t, n, a, b;
int dp[120][120];//dp[n][k]--->n개 성냥개비로 k자리수를 만들수 있는가???
int find(int n, int k) {
	if (dp[n][k] != -1)return dp[n][k];
	if (n < 0)return 0;
	if (k == 1) {
		if (2 <= n && n <= 7)return dp[n][k] = 1;
		else return dp[n][k] = 0;
	}
	if (k == 0) {
		if (!n)return dp[n][k] = 1;
		return dp[n][k] = 0;
	}
	return dp[n][k] = find(n - 2, k - 1) | find(n - 3, k - 1) | find(n - 4, k - 1) | find(n - 5, k - 1) | find(n - 6, k - 1) | find(n - 7, k - 1);
}
vector<int> v;
void ans(int n, int k, bool first) {
	if (!k)return;
	if (!first && find(n - 6, k - 1)) {
		v.push_back(0);
		ans(n - 6, k - 1, false);
	}
	else if (find(n - 2, k - 1)) {
		v.push_back(1);
		ans(n - 2, k - 1, false);
	}
	else if (find(n - 5, k - 1)) {
		v.push_back(2);
		ans(n - 5, k - 1, false);
	}
	else if (find(n - 4, k - 1)) {
		v.push_back(4);
		ans(n - 4, k - 1, false);
	}
	else if (find(n - 6, k - 1)) {
		v.push_back(6);
		ans(n - 6, k - 1, false);
	}
	else if (find(n - 3, k - 1)) {
		v.push_back(7);
		ans(n - 3, k - 1, false);
	}
	else if (find(n - 7, k - 1)) {
		v.push_back(8);
		ans(n - 7, k - 1, false);
	}

}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	//freopen("input.txt", "r", stdin);
	cin >> t;
	memset(dp, -1, sizeof(dp));
	while (t--) {
		cin >> n;
		//cout << 100 - t << '\n';
		//n을 7로 나눈 몫+1이 최소 자리수 이다.
		int cnt = (n - 1) / 7 + 1;
		v.clear();
		ans(n, cnt, 1);
		for (int nxt : v)cout << nxt;
		cout << ' ';

		if (n % 2)cout << "7";
		else cout << "1";
		for (int i = 0; i < n / 2 - 1; i++)cout << "1";
		cout << '\n';
	}
}

snrnsidy 3년 전 0

100

이거 돌리셔서 3일 때 결과확인해보세요

djs100201 3년 전 0

제가 제 코드로 vs에서 돌려본 결과
22 11111
18 7111
10 1111
22 11111
22 11111
188888888888888 11111111111111111111111111111111111111111111111111
10888888 1111111111111111111111111
7
7 7
6 111
이렇게 나오는데 3일 때 7 7 나오는게 맞지 않나요??

혹시 다르게 나오시나요?

snrnsidy 3년 전 1

22 11111
18 7111
10 1111
22 11111
22 11111
188888888888888 11111111111111111111111111111111111111111111111111
10888888 1111111111111111111111111
1 1
2 7
6 111

ideone에서는 최소가 2로 나옵니다

djs100201 3년 전 0

감사합니다 해결했습니다.
10번째 라인과 11번째 라인을 바꾸면 맞습니다...vs에선 음수인덱스에 접근해도 어떻게 잘 되나 보네요..ㅠㅠ

qjsro368 1년 전 0

문제에 있는 테스트 케이스에서 입력이 3이면 7 7인데 왜 2 7이 맞는건가요..?

snrnsidy 1년 전 0

입력이 3이면 7 7이 맞는데, 질문자님께서 올려주신 코드를 돌렸을 때 2 7로 나와서 그걸 말한거였습니다.

qjsro368 1년 전 0

아하 이해했습니다 감사합니다:)

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

문제

문제

출처

ICPC

도움이 절실합니다...

djs100201 3년 전 2

snrnsidy 3년 전 0

djs100201 3년 전 0

snrnsidy 3년 전 1

djs100201 3년 전 0

qjsro368 1년 전 0

snrnsidy 1년 전 0

qjsro368 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말