글 읽기 - 반례를 알고싶습니다..

ideo 5년 전 0

게시판에 나온 반례와 생각해본 반례를 모두 해보았는데 틀렸다고 나오네요

도움 부탁드리겠습니다 ㅠㅠ

import sys
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline().strip())
edge = [[] for i in range(n+1)]#간선관계
dp = [[(-1) for i in range(2)] for ii in range(n+1)]#얼리어답터일 경우와 아닐경우 2가지로 나눠서

for i in range(n-1):
	a,b = map(int, sys.stdin.readline().strip().split())
	if a<b:#작은쪽에서 큰쪽으로 향하는 단방향 간선
		edge[a].append(b)
	else:
		edge[b].append(a)

def func(cur, chk):
	if dp[cur][chk] != -1:#이미 방문했다면 종료
		return dp[cur][chk]
		
	if not edge[cur]:#자식이 없는 노드라면 종료
		dp[cur][chk] = chk
		return dp[cur][chk]
	
	dp[cur][chk] = chk
	ret = 0
	
	if chk == 1:#얼리어답터라면 자식의 얼리어답터의 여부가 상관없음
		for i in edge[cur]:#
			ret += min(func(i,1), func(i,0))#그리고 그중에 최소값을 찾음
	else:#얼리어답터가 아니라면 자식은 얼리어답터여야함
		for i in edge[cur]:
			ret += func(i,1)
	
	dp[cur][chk] += ret
	return dp[cur][chk]
	
print(min(func(1,1), func(1,0)))

ideo 5년 전 1

이유를 찾았네요

바보같이 간선을 연결할때 작은쪽에서 큰쪽으로만 하면 된다고 생각했지만

1 5

2 5

3 5

4 5

같은 경우에는 성립하지가 않겠네요

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

문제

문제

출처

ICPC

반례를 알고싶습니다..

ideo 5년 전 0

ideo 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말