BOJ 1129 - 키
보고 어렵지 않게 바이토닉 투어 DP를 떠올렸고 그렇게 풀었다. 파라메트릭 서치도 썼다.
하지만 굳이 그렇게 안해도 되고 그냥 그리디하게 고려해서 풀 수 있다.
그리고 그 과정이 결국 바이토닉 투어 DP 과정이랑 똑같이 모두 키를 정렬해둔다음 가장 큰 곳으로 가는 과정에서
가는 경로에 붙일 수 있으면 최대한 붙이고 못붙이면 오는 경로에 붙여서 진행한다.
보고 어렵지 않게 바이토닉 투어 DP를 떠올렸고 그렇게 풀었다. 파라메트릭 서치도 썼다.
하지만 굳이 그렇게 안해도 되고 그냥 그리디하게 고려해서 풀 수 있다.
그리고 그 과정이 결국 바이토닉 투어 DP 과정이랑 똑같이 모두 키를 정렬해둔다음 가장 큰 곳으로 가는 과정에서
가는 경로에 붙일 수 있으면 최대한 붙이고 못붙이면 오는 경로에 붙여서 진행한다.
Comments