rnjsxo33   3달 전

가로줄을 선택했을떄의 최대값을 먼저 각각 구한뒤,

최대값들을 다시 세로줄로 선택하는 방법을 실행했는데 시간초과가 납니다.


사탕을 어떻게 하면 더 빨리 주울수 있을까요?

crasy111   3달 전

일단 1차원 배열로 생각하지 말고 2차원 배열로 했을때 어떻게 점화식이 나올지 생각해보세요.

그 후에 vector를 이용해서 2차원 dp를 하셔도되고 1차원으로 해서 위치 계산을 해서 dp를 하셔도되고요.

가로로 줍는 최대값과 세로로 줍는 최대값을 다 dfs를 이용해서 구하셨는데, 이는 당연히 시간초과가 납니다. 가로나 세로가 최악의 경우 N*1 혹은 1*N이 될 수도 있기때문이죠.

시간복잡도 계산은 정확하게는 모르겠지만, 가로의 경우 각 i행에 대하여, j번째 열에서 +2를 할지, +3을 할지인데, 이게 2개중 한개를 선택하는 꼴이어서 2^x 형태로 시간이 걸릴거같습니다.

댓글을 작성하려면 로그인해야 합니다.