이거 문제 왤케 어려움 ㅇㅅㅇ

[익명(118.235)]

구현해도 왠만하면 시간초과 나네 ㅇㅅㅇ

이게 만약 백트래킹으로 하면 치킨집 하나 없애거나 추가할때마다 모든 n개의 집에 대해서 모든 치킨집에 대해 최소거리를 계산해야되는데

뭐냐

[익명(fjw5xqbvqi1x)]

니 컴이 똥컴

[익명(118.235)]

https://www.acmicpc.net/problem/15686

[익명(fjw5xqbvqi1x)]

심지어 백트래킹 문제도 아님

[익명(118.235)]

일단 집이랑 치킨집 따로 벡터에 넣어서 쓰고있는데 말이지..

[익명(fjw5xqbvqi1x)]

연산 많아봐야 50x50x50x50인데 600만개 가지고 시간초과나는게 똥컴이지

[익명(118.235)]

ㅇㅅㅇ;; 저거 치킨집을 n개중에 r개를 선별해야 해서 nCr 조건도 붙삼

[익명(fjw5xqbvqi1x)]

지능문제네

[익명(123.142)]

이건 수학이자낭 대가리 존나굴려바바

[익명(118.235)]

아니 최소거리 구하는거야 당연히 알지.. 근데 연산 횟수가 말도안됨

[익명(123.142)]

어니 니머리로 그 연산횟수를 줄일 수 있게 짧은 수식으로 만들라구..

[익명(183.100)]

2달 전에 푼거라 기억안나긴 하는데 난 백트래킹으로 품 pypy로 300ms정도 나옴

[익명(118.235)]

백트래킹 해도 ㅇㅅㅇ.. ㅠㅠ

[익명(183.100)]

지금보니까 치킨집을 고를 M개 고를 조합 짤때 백트래킹 이용하고 골랐으면 계산해서 최솟값 갱신해나가는거임

[익명(118.235)]

그니까 그렇게 짰는데 시간초과야

[익명(183.100)]

걍 치킨집 조합 + 치킨,집까지의 거리중의 최솟값 끝임

[익명(183.100)]

뭔가 중복해서 하는 계산이 있는거겠지 조합이 아닌 순열로 짰거나

[익명(118.235)]

치킨집 한번 조합하잖아?? 그러면 모든 집에 대해서 가장 가까운 치킨집을 찾아야해 ㅇㅅㅇ.. 집이 20개에 치킨집을 10개 선택하면 집 20개에 대해 각각 모든 치킨집에 대한 거리를 계산해서 최솟값을 찾아야하니까 200번 연산 해야대 그리고 이거를 모든 조합에 대해 구해서 최솟값을 찍어야대

[익명(183.100)]

본문에 치킨집을 없애거나 추가한다는 말은 왜 써놈? 걍 M개만 골라도 되는데 최대 M개를 고르라고는 했지만 실제로 M개 미만으로 택하면 당연히 도시와 치킨거리의 값이 커지니까 답이 될려면 M개를 택하면 됨

[익명(118.235)]

근데 막 1번 치킨집 하나를 없앴을 때 이 1번 치킨집에 영향받는 다른 집이 몇개인지, 치킨거리가 얼마나 줄어들지 이런건 절대 몰라.. 그래서 모든 경우를 다 돌려바야대

[익명(183.100)]

치킨집 조합 최대 13c7 = 1716개 집의 갯수 100개 이하 1716 * 100

[익명(118.235)]

그래서 그렇게 구현했는데 시간초과떠 ㅇㅅㅇ ㅠㅠ

[익명(183.100)]

아니 걍 치킨집 좌표를 설정해 M개 조합으로 그 좌표에 대해서 모든 집의 좌표를 기록한 변수하나 만들어논다음에 그 치킨집좌표와 집좌표 거리 구하고 최솟값을 갱신해나가면 되잖아 치킨집좌표 - 집좌표 절댓값으로 씌워주고

[익명(183.100)]

이해안되면 코드 줘?

[프갤로(gotopg)]

c 는 0ms 네 ㅇㅅㅇ

[익명(118.235)]

자꾸 나 기죽일래 ㅇㅅㅇ?!

[프갤로(gotopg)]

[프갤로(gotopg)]

c로 하란 말이었어..ㅇㅅㅇ

[익명(118.235)]