2274번 - Conflicting Strings
이 문제는 알파벳 형태로 주어진것만 제외하면 일반 그래프에 크기가 k보다 작은 vertex_cover가 존재하는지를 판단하는 문제이고 이는 NP-complete로 알고 있습니다.
현재 ac를 맞은 3명의 코드(저포함) 중 2명은 그리디로 풀었고 당연히 반례가 있습니다. 나머지 한분은 단순 재귀로 풀었으나 '*'이 많은 테스트 케이스를 넣으면 당연하게도 지수 시간복잡도가 되어서 TLE가 뜨게 됩니다.
제가 틀린것이 아니라면 조건 추가나 제한 완화가 필요하다고 생각됩니다.
그리디 반례
5 3aaaababbbc0 0
정답: Yes
tle 저격
input.txt
정답: No
댓글을 작성하려면 로그인해야 합니다.
hulahula3247 3년 전 3
이 문제는 알파벳 형태로 주어진것만 제외하면 일반 그래프에 크기가 k보다 작은 vertex_cover가 존재하는지를 판단하는 문제이고 이는 NP-complete로 알고 있습니다.
현재 ac를 맞은 3명의 코드(저포함) 중 2명은 그리디로 풀었고 당연히 반례가 있습니다. 나머지 한분은 단순 재귀로 풀었으나 '*'이 많은 테스트 케이스를 넣으면 당연하게도 지수 시간복잡도가 되어서 TLE가 뜨게 됩니다.
제가 틀린것이 아니라면 조건 추가나 제한 완화가 필요하다고 생각됩니다.
그리디 반례
5 3
aa
aa
ba
bb
bc
0 0
정답: Yes
tle 저격
input.txt
정답: No