알고리즘 공부하고 있는 학생인데요.
지금 dynamic progamming 문제 하나만 질문할게요
일자로 길게 쭉 뻗은 길위에 작은 구멍가게를 짓는다고 하자.
각각의 가게들의 위치를 x1,x2,..,xi,...,xn이라고 한다.
각 i번째에 있는 가게들로 부터 얻는 수익은 ri (i=1,2,..,n)이다.
각 가게들은 서로 최소 5km 이상 떨어져 있어야한다.
당신은 가게들의 총 수익을 최대로 만들고 싶어한다.
Input: (x1, r1), (x2, r2), (x3, r3), ... , (xn, rn)
(i는 x의 위치에 대한 오름차순으로 정리 되어있다; i가 작을수록 시작점으로부터 가깝다.)
이거 막 알고리즘으로 구멍가게 막 지어서 최대수익나게 하는 알고리즘 만들어야하는데 좀 도와주세요
재귀함수써야 할 것 같은데 1번부터 시작해서 최대한 많이 짓기도 해보고 r(수익)이 가장 큰 애들부터 짓기 해도 안되고...
거의 이틀내내 고민하는데 답이 안나와여..
부탁드릴게요!
D(n): n번째 위치에 가게를 지을때 처음 n 가게에서 날 수 있는 최대 수익
다이나믹 상태까지 알려줬는데 못 풀진 않겠지? 그리고 하나 더 힌트 주면 O(n) 안에 풀 수 있음.
아 정정함. D(n): 그냥 처음 n개의 가게에서 날 수 있는 최대 수익임.
그니깐 n=1일때는 가게가 하나니깐 x1의 수익인 r1의 수익이 최대 수익이고 n=2라면 x1-x2<5일때 r1>r2라면 최대수익=r1, r1<r2라면 최대수익=r2 이런식으로여??? 이거를 divede and conqeur해나가는 건가여???
점화식을 적어봐. 맞는지 아닌지 알려줌.
형 하고 있어요 기다려줘여 어디가면 안되여
아 형 안나와여ㅜ 힌트 좀 주세요
n=3 여기까지만 와도 엄청 복잡해져요ㅠ 수식화가 안되고 있어요
어디가셨어요????????????????????????????
일단 첫번째: D는 증가 함수다. 이건 자명하므로 왜 그런지는 생략. 그럼 귀납법적인 접근으로 D(1), D(2), .. D(n - 1) 값을 구했다고 해보자. D(n) 값을 구하고 싶어. 이때 두가지 선택지가 있겠지. 하나는 n번째 위치에 가게를 짓지 않는거. 그때는 D(n) 값은 D(n - 1) 이 되. 다른 하나는 n번째 위치에 가게를 짓는건데 n번째 위치에 가게를 지으면 인접한 가게와의 거리가 5 km 이상이어야지? 그럼 우리가 구했던 D(i) 값 중 i를 최대화 시키면서 (D는 증가 함수니까) x(n) - x(i) >= 5 를 만족하는 i를 찾으면 되지. 그럼 그때 D(n) 값은 D(i) + r(n) 이 되지. 즉 D(n) = max(D(n - 1), D(i) + r(n)) 이 됨.
그런데 이걸 그대로 구현하면 n 제곱 수행 시간인데 D가 증가 함수라는 성질을 이용해 선형시간으로 만들 수 있음.
x(i) 값이 다 다르다면 그대로 구현해도 선형시간이겠군.
아 가신줄 알았어여ㅜㅜ 감사합니다 말씀하신대로 한번 해볼게요