hdu-4597(๊ฒ์ DP)
๋ ์์ด๊ฐ ๋ชจ๋ ๋๋ํ๊ธฐ ๋๋ฌธ์ ๊ทธ๋ค์ ๋ฐ๋์ ๊ฐ๋ฅํ ํ ์ต์ ์ ๋ฐฉ์์ ์ ํํ ๊ฒ์ด๋ค. ๊ทธ๋์ ๋ชจ๋ ์ฌ๋์ ํ์ฌ์ ์ต์ ์ ๋ค์ ์ฌ๋์ ์ต์ ์ ์์กดํ๋ค.๊ทธ๋ผ ๋ํ ์ผ์ ์ด๋ป๊ฒ ํ ๊น์?์๋๋ฉด ์ผ์ผ๋ฌต์ ๊ณก์กฐ๋ฅผ ๋ค์ ์ฐ์ฃผํ ์ง, ๋จผ์ ์ํ๋ฅผ ์ด๋ป๊ฒ ํ์ํ ์ง, ์ํ๋ฅผ ์ด๋ป๊ฒ ์ฎ๊ธธ์ง ์๊ฐํด ๋ณด์.
์ํ๋ฅผ ์์ ํ๊ฒ ๋ฌ์ฌํ๋ ค๋ฉด, ์ฐ๋ฆฌ๋ ๋ฐ๋์ 4์ฐจ์ ๊ทธ๋ฃน์ ๋ง๋ค์ด ๋ ๋ฌด๋๊ธฐ์ ํ์ฌ ์ํ๋ฅผ ๊ธฐ๋กํด์ผ ํ๋ค.๊ทธ๋ฌ๋ฉด ์ํ๋ d[al][ar][bl][br]๋ก ํ์ํ๊ธฐ ์ด๋ ต์ง ์๋ค. ๋ ๋ฌด๋๊ธฐ์ ์นด๋๊ฐ ํ์ฌ ์๋ฏธ ์ํฉ์์ ์ป์ ์ ์๋ ์ต๋ ์ ์๋ฅผ ๋ํ๋ธ๋ค. ๊ทธ๋ฌ๋ฉด ์ํ๋ ์ด๋ป๊ฒ ์ด๋ํฉ๋๊น?
์์์ ๋งํ๋ฏ์ด ํ์ฌ์ ์ต์ฐํด๋ ์ด์ ์ ์ต์ฐํด์ ์์กดํ๋ค. ์๋ํ๋ฉด ๋ ์์ด๊ฐ ๋ชจ๋ ๋๋ํ๊ธฐ ๋๋ฌธ์ด๋ค.์ถDP๋ ํญ์ ์ปจ๋์ ์ด ๋ฌด์์ ํ์ํ๋์ง ์ฃผ์ํด์ผ ํ๋ค. ๋ฐฉ๊ธ ์ด ์์ด์ ์ต๋ ์ ์๋ฅผ ํ์ํ๋ค๊ณ ํ๋๋ฐ ์ด๋ป๊ฒ ๊ตฌํ์ง?๋ถ๋ช ํ ์ด์ ์์ ๋ค์ ์์ด์ ๋์ ์ ๋นผ๊ณ ๋ค์ ์์ด์'์ด์ '์ ํ์ฌ ์์ด๊ฐ ๊ฐ์ ธ๊ฐ ํจ๋ฅผ ๋นผ์ผ ํ๋ค.
์์ธํ ์ฐธ๊ณ ์ฝ๋:
#include
using namespace std;
int T,n,d[25][25][25][25],a[25],b[25];
int dp(int al,int ar,int bl,int br,int sum) {
int& ans = d[al][ar][bl][br];
if(ans != -1) return ans;
ans = 0;
if(al<=ar) {
ans = max(ans,sum-dp(al+1,ar,bl,br,sum-a[al]));
ans = max(ans,sum-dp(al,ar-1,bl,br,sum-a[ar]));
}
if(bl<=br) {
ans = max(ans,sum-dp(al,ar,bl+1,br,sum-b[bl]));
ans = max(ans,sum-dp(al,ar,bl,br-1,sum-b[br]));
}
return ans;
}
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
int sum = 0;
memset(d,-1,sizeof(d));
for(int i=1;i<=n;i++) scanf("%d",&a[i]) , sum += a[i];
for(int i=1;i<=n;i++) scanf("%d",&b[i]) , sum += b[i];
int ans = dp(1,n,1,n,sum);
printf("%d
",ans);
}
return 0;
}
์ด ๋ด์ฉ์ ํฅ๋ฏธ๊ฐ ์์ต๋๊น?
ํ์ฌ ๊ธฐ์ฌ๊ฐ ์ฌ๋ฌ๋ถ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ AI ์์ง์ ๋จธ์ ๋ฌ๋ ๋ถ์(์ค๋งํธ ๋ชจ๋ธ์ด ๋ฐฉ๊ธ ๋ง๋ค์ด์ ธ ๋ถ์ ํํ ๊ฒฝ์ฐ๊ฐ ์์ ์ ์์)์ ํตํด ๊ฐ์ฅ ์ ์ฌํ ๊ธฐ์ฌ๋ฅผ ์ถ์ฒํฉ๋๋ค:
์กฐ๋ฐํ ๊ฒ์์ Scratch๋ก ๋ง๋ค์ด ๋ณด์๋ค. ๊ทธ 1.2021๋ 1์ 7์ผ์ ์ค๊ฐ ์ด๋ฆฌ๊ฐ ๊ธด๊ธ ์ฌํ ์ ์ธ์ ๋ฐ๋ นํ์ต๋๋ค. ์ญ์ ใ๋ฐใ์ด ์ข์ง ์์ ์ผ์ด๋ผ๊ณ , ์ฌ์ฐจ ์๊ฐํ์ผ๋ฏ๋ก ๋ท์์ ๋ณด์ธ ๋ช ์ ์ ๋ง์๋๋ก ํ๋ด๋ด Scratch๋ก ๋ง๋ค์ด ๋ณด์์ต๋๋ค. <์์ฑ ์ด๋ฏธ์ง> ๋งํฌ...
ํ ์คํธ๋ฅผ ์์ ๋กญ๊ฒ ๊ณต์ ํ๊ฑฐ๋ ๋ณต์ฌํ ์ ์์ต๋๋ค.ํ์ง๋ง ์ด ๋ฌธ์์ URL์ ์ฐธ์กฐ URL๋ก ๋จ๊ฒจ ๋์ญ์์ค.
CC BY-SA 2.5, CC BY-SA 3.0 ๋ฐ CC BY-SA 4.0์ ๋ฐ๋ผ ๋ผ์ด์ผ์ค๊ฐ ๋ถ์ฌ๋ฉ๋๋ค.
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค