시간복잡도가 N^2M이 나오기 때문에 시간 초과를 받게 됩니다.
채워야 하는 테이블의 개수는 N*M개 인데, 28번 줄에서 for를 i/2까지 돌아버리기 때문에 각각의 칸을 채우는 시간복잡도가 O(N)이 되어버립니다.
© 2018 All Rights Reserved. 주식회사 스타트링크 |
서비스 약관 |
개인정보 보호 |
결제 이용 약관 |
도움말 |
광고 문의 |
대회 개최 문의
사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 강남대로 359 대우도씨에빛2 5층 502호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: [email protected]
통신판매신고번호: 제 2017-서울서초-2193 호
이 사이트는 ACM 또는 ACM-ICPC 대회와 무관하며, ACM으로부터 승인이나 지원을 받지 않고 있습니다.
thkighie1224 2년 전
Memorization 으로 풀었는데요 ㅜ.ㅜ
시간 초과가 뜨네요...
가로 7 세로 3 인 경우
Cache[7][3] = (Cache[6][3]+Cache[1][3]) , (Cache[5][3]+Cache[2][3]) , (Cache[4][3]+Cache[3][3]) , (Cache[7][1]+Cache[7][2]) 중에서 작은 걸 고르는 식으로 계산 했습니다.
위와 같이 모든 경우를 다 계산 할 필요가 없는 문제인가요? 아니면 Memorization으로 풀면 안되는 문제인건가요 ㅜ.ㅜ?