[일반] 어제자 GBS

[C751AE3..(114.203)]

대충 9:40 쯤 하고 있길래 쭉 풀어보려고 했는데

들어갔는데 B1부터 그리디인거 보고 뇌저려서 튀었음 ㅋㅋ

[익명(211.234)]

디피로도가능

[C751AE30C787(114.203)]

DP N^2에서 줄일 수 있음?

[익명(180.70)]

나는 그리디로 풀린다는 거 못찾아서 dp로 푼 바보인데, 이전에 나왔던 산들 중에서 어떤 산이랑 이을지 고를 때, 만약 높이가 같은 산들이라면 무조건 현재 산으로부터 거리가 가까운 (즉 그나마 최근에 나온 산) 걸 이어주는 게 무조건 이득이기에 각 높이별로 가장 최적인 산들만 저장해서 비교해줬음 그러면 시간복잡도는 N * 100 될테니 통과가능

[익명(221.147)]

이 풀이 안 나올 줄 알고 안 막음 ㅋㅋ

[C751AE30C787(114.203)]

두시간 전에 푼 플래랑 똑같은 문제였노 ㅋㅋ ㅅㅂ 개같네