cheetose   4년 전

d[i][j]=d[N번째 적][죽인 적] 이라고 하고

d[i][j] 테이블을 채울 때 d[k][j-1] (k=j-1 to i-1)과 d[k][j] (k=j to i-1)를 비교해가면서 stat.total이 최소가 되는 값으로 계속 업데이트 해줬는데 잘못된 방법인가요..? 혹시 이게 잘못된 방법이라면 어떤 식으로 접근해야할지 힌트라도 주실 수 있나요..??

lyzqm   4년 전

저도 이렇게 접근했는데 계속 틀렸다고 나오네요 ㅎㅎ;;

ainch96   4년 전

능력치 좌표 압축 시킨 다음 ( sort + binary search ) , for문 3번 돌면서, ( i,j,k : 각각의 능력치 인덱스 값 ) 

각 구간안에 들어 있는 병사의 수가 K보다 이상이면, 업데이트 해주는 식으로 하면... 

( 병사의 수는 dp 전처리를 통해서 O(1) 만에 구하고 )

시간 : O(n ^ 3 ) / 공간 : O ( n ^ 3 ) 만에 구할 수 있을 것 같습니다. 

반례가 당장 떠오르지는 않지만 분명이 있을 것 같습니다. 능력치 3개의 합이 더 크더라도 

뒤에 오는 값을 포괄하기에 유리한 케이스가 존재할 것 같습니다. 지금 학교 실습 마치면 만들어 보겠습니다. 

cheetose   4년 전

으... 제가 멍청해서 능력치 좌표 압축시킨다는 말을 이해를 못하겠어요 ㅠㅠ

jason9319   4년 전

좌표압축 기법은 이 문제의 경우 수의 범위가 0~100만이므로 모든 힘 민첩 지능에 대해 100만 ^3 으로 탐색을 하면 너무 많은 시간이 걸리므로

입력에 등장하는 숫자들만 가지고 탐색을 하는겁니다. 

수의 범위는 100만이지만 나올 수 있는 최대 수는 100개 밖에 안되기 때문이죠 따라서 100 ^3으로 가능한 모든 답의 후보를 만들 수 있습니다.

jason9319   4년 전

예를들면 이런식으로 입력을 벡터들에 저장하여 저 수들만 확인해주는걸 아마 좌표압축이라고 부를겁니다. (보통은 등장하는 수에 고유의 번호를 매겨주기 위해 사용됩니다.)

cheetose   4년 전

아아아 자세한 설명 너무 감사드립니다 ㅠㅠ 다시 한 번 풀어볼게요!! 덕분에 새로 하나 배웠네요 ㅎㅎ

ainch96   4년 전

헐 너무 늦게 봤네요 죄송니다. 
대신 친절하게 설명해주신

jason9319   

님 감사합니다. 

cheetose   4년 전

음.. 한번 O(n^4)로 제출해봤는데 왜 매우 여유롭게 AC가 나오는지 모르겠네요.. 암튼 덕분에 풀긴 풀었네요 ㅋㅋㅋㅋㅋㅋ 두분 다 너무 감사합니다

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