27163번 - 벚꽃 내리는 시대에 결투를
지금까지의 경로를 전부 저장하면서 경로를 구하는 방식으로는 시간내로 돌아갈 수 없습니다.
예를 들어, N이 5000이면 정답에 해당하는 경로의 길이가 5000이 될텐데 이 경로를 얻기 위해서만 길이가 1부터 5000까지, 총 길이가 1000만이 넘는 문자열을 만들어줘야 합니다.
당연히 정답에 해당하는 경로 외의 경로에 대해서도 문자열을 만들어주기 때문에 실제로 필요한 문자열의 길이는 매우 커지게 됩니다.
경로를 구하기 위해서는 먼저 dp배열을 만들어주고, 만들어진 dp배열을 이용해 경로를 역추적해줘야 합니다. 여러 문제에서 등장하는 테크닉이니 찾아보시면 될 것 같습니다.
해결했습니다. 조언 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
kwonsy1446 2년 전 0
N/L
0 1 2 3 4 54
예제인
3 4 5
1 2
4 5
0 2에 대한 cache 배열입니다.
cache 한 칸을 채우려면 X/Y(X와 Y 모두 -1이 아니라는 가정 하에) 공격에 대해 2가지 값을 비교하면 됩니다. cache[i][j]에 대해
1. cache[i-1][j] - X (이 값이 0보다 작으면 -1로 생각) // X로 공격을 받는 경우
2. cache[i-1][j+Y] (인덱스가 넘어가는 경우, -1로 생각) // Y로 공격을 받는 경우
이 2개의 최댓값으로 cache 배열를 갱신해 나가고, tracking 배열에 지금까지의 경로를 저장했습니다.
( X/ -1이나 -1 / Y의 경우는 한 가지 경우만 생각하면 됨)
cache 한 칸을 채우는데 상수 시간이 걸리므로 시간 복잡도는 O(NL)이라고 생각했는데, 시간 초과가 뜨네요..
코드의 최적화 문제인가요? 아니면 특정 테크닉을 통해 시간 복잡도를 로그 시간으로 줄일 수 있나요?
한 칸을 채울때 비교 연산이 많아서 상수 계수가 문제가 되는 거 같기도 하고..
답변 부탁드립니다.