글 읽기 - [c++] 어디가 틀렸는지 모르겠습니다..!

sally0226 2년 전 0

흠.. input을 이것저것 만들어서 넣어봤는데 반례도 찾을 수 없었습니다ㅜㅜ 문제가 뭘까요

#include <iostream>
#include <vector>

using namespace std;

int N;
struct Node {
	int input_num=0; //0:접근불가, -1:노드넣기가능, 1이상:이미 채워짐
	int value;
	bool left=false; 
	bool right=false;
};
Node nodes[300001];
vector<int> input_idx;	

int pow(int n) {
	int result = 1;
	for (int i = 0;i < n;i++) {
		result *= 2;
	}
	return result;
} 

int idx = 1;
void inOrder(int i) {
	if (nodes[i].left) inOrder(i * 2 + 1);
	//cout << "i:"<<i<<" idx :" << idx << endl;
	nodes[i].value = idx++;
	if (nodes[i].right) inOrder(i * 2 + 2);
}
int main() {
	// 트리 만들어놓고 중위순회 하면서 방문순서대로 매기면 되는건가 
    // 트리노드에 입력순서도 넣어놓기
	cin >> N;
	nodes[0] = { 0,0,false,false };
	nodes[1] = { -1,0,false,false };
	nodes[2] = { -1,0,false,false };
	input_idx.push_back(0); // root넣어주기 
	int flag;
	for (int n = 1;n < N ;n++) {
		int depth;
		cin >> depth;
		int start = pow(depth) - 1;
		int end = pow(depth+1)-2;
		flag = true;
		for (int i = start;i <= end;i++) {
			if (i > 300000) break;
			//이미 노드가 들어간 곳이거나 아예 넣지 못하는 곳은 pass
			if (nodes[i].input_num != -1) continue;
			int parent;
			// 홀수는 left자식, 짝수는 right자식 
			if (i % 2 == 0) {
				parent = (i / 2) - 1;
				nodes[parent].right = true;
			}
			else {
				parent = (i - 1) / 2;
				nodes[parent].left = true;
			}
			nodes[i].input_num = n;
			input_idx.push_back(i);
			// 자식 input_num -1로 초기화 해줘야함 
			if (i * 2 + 1 <= 300000) nodes[i * 2 + 1].input_num = -1;
			if (i * 2 + 2 <= 300000) nodes[i * 2 + 2].input_num = -1;
			flag = false;
			break;
		}
		if (flag) {
			cout << -1 << endl;
			return 0;
		}
	}
	// 중위순회하면서 순서 매기기 (value담기)
	inOrder(0); 
	for (int i = 0;i < input_idx.size()-1;i++) {
		cout << nodes[input_idx[i]].value << " ";
	}
	cout << nodes[input_idx[input_idx.size() - 1]].value << endl;
	return 0;
}

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

문제

문제

출처

ICPC

[c++] 어디가 틀렸는지 모르겠습니다..!

sally0226 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말