[일반] 스도쿠 백트래킹해도 tle아닌 이유가 뭔가요

[유고등(flowable)]

2580번이나

https://www.acmicpc.net/problem/2580

2239번같은 문제

https://www.acmicpc.net/problem/2239

처음 ps할때 아무생각없이 백트래킹으로 긁어서 2580번 ac받았었는데, 2239번으로 다시 보니 왜 맞은건지 의아함

그냥 퍼즐 특성상 예외적인 엣지케이스가 없다하고 그러려니 넘기면되나,,,

[mod998244353(dontbeaccused)]

https://stackoverflow.com/questions/24682039/whats-the-worst-case-valid-sudoku-puzzle-for-simple-backtracking-brute-force-al

[유고등(flowable)]

그냥 worst case찾는내용이 전부인거같은데 맞음?

[익명(223.62)]

그런당신을위한
https://www.acmicpc.net/problem/1840

[유고등(flowable)]

[익명(223.33)]

엣지케이스가 물론 있는데 위 2개 문제는 백트래킹으로 가능한 입력만 주어짐

[익명(223.33)]

12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다. C++14: 80ms Java: 292ms PyPy3: 1172ms

[유고등(flowable)]

ㅇㅎ 그래서 저런제한이걸려있구나

[익명(211.243)]

전부다비우거나 아래부터 채우면 절대 안끝남 ㅋㅋㅋㅋ - dc App