글 읽기 - 누적합을통해 해결할 수 있을거 같아 풀었는데 시작과 동시에 실패를합니다.

shfshfdl 6년 전 2

다른분들은 dfs나 이런것을 통해 풀었는데, 전 누적된 값을 미리 다 정해놓으면

그 값을 제거했을때 root에 뺄값이 정해질 수 있을거같아 아래와 같이 풀었습니다.

질문에 있는 반례들을 모두 해봣는데 통과하는거 같구요...

dfs말고 이방법으로 해결을 해보고싶은데 틀린점을 찾지 못하겠네요

도움주시면감사하겠습니다.

#include <stdio.h>

#define MAXN 51
int N;
int parent[MAXN] = { 0, };
int childCnt[MAXN] = { 0, };
int root;

int main(void){
	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &parent[i]);
		if (parent[i] == -1) {
			root = i;
			continue;
		}

		childCnt[parent[i]]++;
	}
	int stop;

	for (int i = 0; i < N; i++) {
		if (childCnt[i] >= 2) {

			int p = parent[i];
			while (p != -1) {
				childCnt[p] += childCnt[i] - 1;
				p = parent[p];
			}
		}
	}

	int deleteNode;
	scanf("%d", &deleteNode);
	int reculsiveSub;

	if (childCnt[deleteNode] == 0) childCnt[deleteNode] = 1;

	int parentNode = parent[deleteNode];

	if (childCnt[deleteNode] == childCnt[parentNode]) {
		reculsiveSub = childCnt[parentNode] - 1;
	} else {
		reculsiveSub =  childCnt[deleteNode];
	}

	int ans = childCnt[root] - reculsiveSub;

	printf("%d\n", ans);

	return 0;
}

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

문제

문제

출처

ICPC

누적합을통해 해결할 수 있을거 같아 풀었는데 시작과 동시에 실패를합니다.

shfshfdl 6년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말