백준 2229번을 풀고, 처음 접근법에 대해서 시간초과가 나서 질문글을 올렸으나,
따로 답변이 달리지 않아 고수분들이 많이 계신다 해서 질문글 올려봅니다. (아래는 질문글입니다.)
도움 주신다면 정말 감사드립니다.
https://www.acmicpc.net/board/view/135676
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net[일반] 안녕하세요 ps 초보 top down dp 시간복잡도 도움 부탁드립니다
익명(180.65)
2024-02-09 10:19
추천 0
댓글 2
다른 게시글
-
너네는 각각 ps 입문이 언제임? [8][일반] 익명(58.237) | 24.02.09추천 0
-
가족 보러 가기 vs 버추얼 [4][일반] 익명(118.235) | 24.02.09추천 3
-
다들 새해 복 많이 받아라. [3][일반] 익명(118.235) | 24.02.09추천 13
-
코포 2개월차[일반] 익명(220.80) | 24.02.09추천 0
-
컴공인데 알고리즘 말고 DB는 어떻게 공부해야하냐 [3][일반] 익명(125.182) | 24.02.09추천 0
-
몃퍼센트 틀렸습니다인지 어케앎 [3][질문] 익명(220.80) | 24.02.09추천 0
-
물플5 이제 코테 준비 제대로 하려고 실렌디 돌리는데 [5][일반] ㅇㅇㅇ(39.124) | 24.02.08추천 0
-
여기 형들은 코테 목표 아니고 그냥 취미로 푸는거지? [6][일반] 익명(58.237) | 24.02.08추천 0
-
백준 1068 C언어입니다. 뭐가 문제일까요 [3][일반] asdf(223.38) | 24.02.08추천 0
-
씨발 [3][일반] ㅁㄴㄹㅇ(58.78) | 24.02.08추천 1
해당 댓글은 삭제되었습니다.
감사합니다! 글을 올리고 종만북에서 top down 시간복잡도에 대해서 찾아보니 (부분 문제의 수) * (dfs 내부 반복문의 횟수)로 표기되어 있어서 부분문제의 갯수 : n개 (i = 1 ~ n) * n개 (e = 1 ~n) = n^2 반복문의 횟수: n^2 이라 O(n^4)이라 결론 내리고 실제로 n = 500을 돌려보니 1초 이상이 걸리더라구요! 확신은 없었는데 댓글 남겨주신거 보고 어느정도 시간복잡도 계산하는 법을 깨우친 것 같습니다. 감사합니다.