글 읽기 - sort 관련 질문입니다.

dlfrk7 3년 전 0

해당문제를 dfs로 풀때

sort를 할 경우 풀리고 sort를 하지 않을 경우 풀리지 않는 이유가

" 일곱 난쟁이의 키를 오름차순으로 출력한다. " 때문인가요..?

입력에 주어진 " 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. " 때문에 꽤나 헷갈렸습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> height;
int check[7] = { 0 };
bool flag = false;

void dfs(int x, int d, int cnt) {

	if (flag == true) return;

	if (d == 7) {

		int sum = 0;
		for (int i = 0; i < 7; i++) {
			sum += height[check[i]];
		}
		if (sum == 100) {
			for (int i = 0; i < 7; i++) {
				cout << height[check[i]] << "\n";
			}
			flag = true;
			return;
		}
		return;
	}

	for (int i = x; i < 9; i++) {
		check[cnt] = i;
		dfs(i + 1, d + 1, cnt + 1);
	}

}

int main() {
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);

	for (int i = 0; i < 9; i++) {
		int temp;
		cin >> temp;
		height.push_back(temp);
	}

	sort(height.begin(), height.end());

	dfs(0, 0, 0);

	return 0;
}

wjdgud0621 3년 전 0

정렬된 결과도 여러 개가 있을 수 있습니다

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

문제

문제

출처

ICPC

sort 관련 질문입니다.

dlfrk7 3년 전 0

wjdgud0621 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말