[일반] G번 뭐지...

[익명(59.16)]

50분을 갈았는데 결국 못풀었어

DP인가? 했는데 그냥 DP로 하면 시간복잡도 터질거같은데...

뭐 최적화라도 필요한건가?

아니면 점화식이 틀린건가?

DP 테이블 인자가 뭐뭐 들어가야하지...

난 위치, 마지막 값, 현재 위치까지의 합으로 잡으면 된다고 생각했는데

이것보다 좋은 방법이 있는건가

[대학원오지마세요(publfl)]

DP맞음. 공간 nm^2 시간 nm^3 DP가되서 시간 터진다고 생각하기 쉬운데 사실 공간 m^2logm밖에 안쓰기 때문에 시간이 m^3logm이라 통과됨

[익명(59.16)]

헐

[대학원오지마세요(publfl)]

님이 잡은 DP식을 보면 현재까지의 합 <= 현재 위치 x 마지막 값을 만족해야해서, 그 부분만 쓰는 공간 계산해보면 m^2logm임 nm^2이 아니라

[익명(59.16)]

와 그렇구나... 부등식 뭔가 나오길래 그렇구나 하고 넘어갔었는데, 그게 시간복잡도의 차이가 되는줄은 몰랐네.... 감사함니다