9574m   4년 전

그래프적 해법이 생각이 안나서 상향 DP를 이용해서 코드를 짰습니다.

배열을 200000개 잡은 것은 20만 번째에는 어떤 좌표가 들어가도 최소에 해낼 수 없기 때문입니당.

문제가 뭘까요?

chogahui05   4년 전

이 경우에 반례 케이스가 나오네요.

2374 28347


dp식을 어떻게 만드셨나요?

chogahui05   4년 전

그래프적 해법은 어렵게 생각하실 필요가 없어요.

3번 지점하고 연결이 되어 있는 것은 2, 4, 6이잖아요. 단방향으로


그러면 연결 시키면 됩니다.

[3][2] = connect. [3][4] = connect. [3][6] = connect.

다만, 노드의 수가 10만개이므로, 인접 배열로 관리하는 건 힘들고요. 인접 리스트로 관리를 하는 게 좋겠지요.

보통 vector로 많이 코딩하십니다.

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