[질문] 문제만 보고 완탐인지 그리디인지 DP인지 구분하는건 하다보면됨?

[익명(220.85)]

학식이 모르겟오요

[익명(223.33)]

걔네를 하나의 접근 방식으로 보고 비슷하게 풀어나갈 수 있는지 직문제를 바꿔보면 됨.

[익명(223.33)]

완탐으로 돌렸는데 안되네? 혹시 이 부분은 무조건 뭐를 선택해도 최적해가 나오나? 중복되는 부분 문제가 있나?

[익명(118.235)]

지금 딱 그런식으로 하는중인데 완팀 안되면 그리디 해보고 안되면 dp 해보고.. 근데 나중이 시간안에 못풀까봐 ㅠㅠ

[익명(223.33)]

시간복잡도 계산할줄 알지? 너가 대회나갈 수준에서 이런 질문을 하는건 아닐테니 코테면 충분히 시간 됨. 최악으로 계산했을때 어느정도 시간 복잡도면 통과가능한지 보면 쉽다

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(118.235)]

쉽지않구만

[익명(211.209)]

제 기준에서는 문제의 제한 n개수 기준으로 놓고 봄. 주어진 개수가 적어서 n^2도 가능하면 걍 완탐돌리고 완탐에서 최적화 여지가 있는 애들은 DP 그리디는 문제가 약간 변태같아서 눈치로 아는듯. 근데 그리디는 증명 개빡세서 앤간하면 안나오지 않을까 싶은데.

[익명(211.209)]

DP는 눈에 잘 안들어오긴 하는데, 점화식 써서 최적화 가능한 케이스인지부터 해보시면 감이 올수도..?

[익명(175.209)]

완탐 -> 오래걸릴 것 같은 반례 생각나면 캐시 추가 -> 뭔가 이상하면 DP -> 그리디 -> 어려움 대충 이런느낌

[MetaFibonacci(equivalence)]