글 읽기 - 2903번 일곱 난쟁이 질문

starplaton 4년 전 0

답이 여러개인 반례도 시도해 보았는데 정답이 잘 나왔습니다..

무엇이 문제인지 알려주실 수 있으신가요? ㅠㅠ

#include <iostream>
#include <algorithm>

using namespace std;

int map[10];
int visited[10];
bool flag = true;

void DFS(int cur, int many, int sum) { // cur : 현재 위치, many : 난쟁이 수, sum : 키의 합
	visited[cur] = 1; // 방문체크 
	if (many == 7 && sum == 100 && flag) {  //정답 찾았을 때
		for (size_t i = 1; i < 10; i++)
		{
			if (visited[i] == 1) cout << map[i] << endl;
		}
		flag = false; // 정답은 1개만 print
		return;
	}
	if (many == 7) return;
	for (size_t i = 1; i <= 9; i++)
	{
		int target = cur + i;
		if (target >= 10) continue; // 범위를 벗어나는 경우
		DFS(target, many + 1, sum + map[target]); // DFS
	}
	visited[cur] = 0; // 방문해제
}

int main(int argc, char* argv) {
	for (size_t i = 1; i <= 9; i++)
	{
		cin >> map[i];
	}

	sort(map, map + 10);
	DFS(0, 0, 0);
	return 0;
}

eovh1962 4년 전 0

void DFS(int cur, int many, int sum) { // cur : 현재 위치, many : 난쟁이 수, sum : 키의 합
	
	if (many == 7 && sum == 100 && flag) {  //정답 찾았을 때
		for (size_t i = 1; i < 10; i++)
		{
			if (visited[i] == 1) cout << map[i] << endl; //여기서 문제가 발생하지 안을까요...??
		}
		flag = false; // 정답은 1개만 print
		return;
	}
	if (many == 7) return;
	for (size_t i = 1; i <= 9; i++)
	{
		int target = cur + i;
		if (target >= 10) continue; // 범위를 벗어나는 경우
		if (!visited[target])
		{
			visited[target] = 1; // 방문체크 
			DFS(target, many + 1, sum + map[target]); // DFS
			visited[target] = 0; // 방문해제
		}
		
	}
	
}

starplaton 4년 전 0

방문체크가 문제였습니다 감사합니다 ㅎㅎ

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

문제

문제

출처

ICPC

2903번 일곱 난쟁이 질문

starplaton 4년 전 0

eovh1962 4년 전 0

starplaton 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말