코그 3번 어캐함?

[익명(143.248)]

생수를 k개 이상 확보해야 되기 땜에
Cost만 고려한 dp로 못풀잖아
생수 주는 모든 vertice에 대해
K combination가지고
K개 중간 경유지 있는 dp풀면 시간 초과될 것 같고

[ㅁㄴㅇㄹ(203.152)]

3차원배열 선언한다음에 세번째 차원을 생수의 개수로해

[ㅁㄴㅇㄹ(203.152)]

그다음에 걍 이중포문돌리는데 각각의 좌표에서 왼쪽과 아래만 계산하면되는데 생수의 개수가 같으면 최소값저장하고 생수 K 개 이상일땐 걍 다 K개일때로 보고 다 같게취급하고 이런식으로하면 O(N^2) 으로 풀림

[익명(121.169)]

2차원 배열로 x,y위치에 생수가 K개 이상일때를 만족하는 lookup table 만들어나가면 O(n^2)에 가능

[ㅁㄴㅇ(58.123)]

잉 나는 그렇게 풀고도 176점이던데 그럼 이럴땐 어떻게함? 왼쪽과 아래에서 한쪽이 생수가 많은대신 고도가 더 높게 계산될때

[ㅁㄴㅇㄹ(58.123)]

답변줘요 형!

[익명(121.169)]

lookup table을 2개 중 min으로 채워나가면 마지막 값이 최소로 나옴

[ㅁㄴㅇ(58.123)]

최소로 나오면 최솟값이 K에 못 미칠때는 어떻게 하나요?