글 읽기 - 17225번 질문드립니다.

wlsth1004100 4년 전 0

안녕하세요 두시간동안 규칙찾다가 계속 막혀 멘탈나가서

결국 dfs로 모든경우를 탐색하고 Map에 만든N문자열을 저장해 중복체크하면서 답을구했습니다.

제가 생각하는 모든케이스는 다잘되는데 어디서 틀렸는지 찾질못해 막막하네요 ㅠ

반례나 틀린점좀 지적부탁드립니다 !!!

#include<cstdio>
#include<string>
#include<string.h>
#include<vector>
#include<map>
#include<iostream>

using namespace std;

int cnt, ans = 0;
bool visited[10];

string str, make_N;

map<int, string> Map;

void dfs(int x)
{
	bool flag = true;

	for (int i = 0; i < cnt; i++) {
		if (!visited[i]) {
			flag = false;
			break;
		}
	}
	if (flag) { // N을 만듬
		for (int i = 0; i < ans; i++) {
			if (make_N.compare(Map[i]) == 0) { // 이미 만들어진 N문자열
				return;
			}
		}
		Map[ans] = make_N; // 새로운 N문자열 맵에저장
		ans++; 
		return;
	}
	for (int i = x + 1; i < cnt; i++) { // rightSearch
		if (visited[i - 1] && !visited[i]) {

			visited[i] = true;
			make_N.push_back(str[i]);

			dfs(i);

			make_N.pop_back();
			visited[i] = false;
		}
	}

	for (int i = x - 1; i >= 0; i--) { // leftSearch
		if (visited[i + 1] && !visited[i]) {

			make_N.push_back(str[i]);
			visited[i] = true;

			dfs(i);

			make_N.pop_back();
			visited[i] = false;
		}
	}
}

int main()
{
	cin >> str;
	cnt = str.size();

	if (str.at(0) == '-' || str.at(0) == '0')
		return 0;
	for (int i = 0; i < cnt; i++)
	{
		memset(visited, 0, sizeof(visited));

		make_N.push_back(str[i]);
		visited[i] = true;

		dfs(i);

		make_N.pop_back();
		visited[i] = false;
	}
	printf("%d", ans);
	
	return 0;
}

vegatrash 4년 전 2

저도 이거 한참 고민하다가 방금 통과했는데요... 지금 자러 가야해서 코드는 못봐드리는데

제가 푼 과정을 설명드리자면 이렇습니다.

모든 순열을 출력하는 n과 m문제 백준에 있는거 아시나요? 그거랑 비슷한 방식으로

좌우로 이동하는 재귀함수를 짰는데요

이동할때마다 현재 진행상황을 string 형태로 저장했습니다 무슨말인가 하면....

421을 찾는데 2 - 42- 421 이렇게 순서로 찾아서 끝까지 왔으면 string에는 242421이 저장되어 있어요

이걸 좌우가 이동할곳이 없어졌을때 unordered_set에 insert했어요

그리고 마지막에 이 set의 크기만 출력해주면 됩니다.

wlsth1004100 4년 전 0

저도 vega님이 말씀하신 방법과비슷하게

좌우를 재귀로검색해서 string에 담고 N개 도달햇을때 중복체크후 map에담는형식으로 코딩햇습니다.

제가 생각하는 케이스다 통과하고 중복체크도 문제없는데 어디서틀렷는지 모르겟네요 ㅠㅠ

혹시시간되시면 제코드좀 봐주시면 감사하겠습니다

vega 4년 전 5

vegatrash님 반갑습니다.

wlsth1004100 4년 전 0

vega님 반례나 틀린점 조언좀부탁드립니다..

vega 4년 전 1

저두... vegatrash님 풀란대로 대충짯더니 맞았습니다... 똑같이 하셨으면..흠..

joonas 4년 전 2

N= 808

output= 2

answer= 4

참고로 여명808과는 무관합니다.

vegatrash 4년 전 1

출제자님 제가 푼 방법이 원래 의도한 풀이가 맞나요? 첨엔 중복조합이나 중복 순열인가 싶었는데 그것도 아닌것 같고 그냥 시뮬레이션으로 풀었는데 과연 이게 맞는가 싶어서요

joonas 4년 전 1

네. 시뮬레이션 맞아용

wlsth1004100 4년 전 2

저는 결과값중복만 확인했는데 결과값과정만드는 과정을 봐야한다는걸 캐치못했네요 ㅠㅠ

댓글달아주신분 덕분에 많은걸 배운것같습니다!

joonas 4년 전 1

아뇨. 풀어주셔서 제가 감사합니다

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