hdu 5092 Seam Carving(dp)
์ ๋ชฉ ๋์: NโM์ ํ๋ ฌ์ ์ ํ์ฌ ๋งค๋ฒ ์๋ ์ธ ๋ฐฉํฅ์ผ๋ก ์ด๋ํ ์ ์๋๋ก ํ๋ค. ํ์ฌ ์๊ตฌํ๋ ๊ฒฝ๋ก์ ๊ฐ์ ๊ฐ์ฅ ์๊ณ ์ต๋ํ ์ค๋ฅธ์ชฝ์ผ๋ก ๊ฐ์ผ ํ๋ค.
์ถ๋ ฅ ๊ฐ๊ณผ ๊ฒฝ๋ก.
๋ฌธ์ ํ์ด ์ฌ๊ณ ๋ฐฉ์: dp[i][j]๋ i์ธต j๋ก ์ด๋ํ๋ ์์น๊ฐ ๊ฐ์ฅ ์ข์ ๊ฒ์ ์๋ฏธํ๊ณ r[i][j]๋ ์์ธต์ ์ด๋ ์์น์์ ์๋์ง ๊ธฐ๋กํด์ผ ํ๋ค.๋ฌผ๋ฌธ์
๋ง์
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 105;
const int inf = 0x3f3f3f3f;
int N, M, g[maxn][maxn], dp[maxn][maxn], vi[maxn][maxn];
void init () {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
scanf("%d", &g[i][j]);
// memset(vi, -1, sizeof(vi));
memset(dp, 0, sizeof(dp));
}
void solve () {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
int x = dp[i-1][j], y = j;
if (j > 1 && dp[i-1][j-1] < x) {
x = dp[i-1][j-1];
y = j-1;
}
if (j < M && dp[i-1][j+1] <= x) {
x = dp[i-1][j+1];
y = j+1;
}
dp[i][j] = x + g[i][j];
vi[i][j] = y;
}
}
int ans = dp[N][1], idx = 1, pos[maxn];
for (int i = 2; i <= M; i++) if (dp[N][i] <= ans) {
ans = dp[N][i];
idx = i;
}
for (int i = N; i; i--) {
pos[i] = idx;
idx = vi[i][idx];
}
for (int i = 1; i <= N; i++)
printf("%d%c", pos[i], i == N ? '
' : ' ');
}
int main () {
int cas;
scanf("%d", &cas);
for (int kcas = 1; kcas <= cas; kcas++) {
printf("Case %d
", kcas);
init();
solve();
}
return 0;
}
์ด ๋ด์ฉ์ ํฅ๋ฏธ๊ฐ ์์ต๋๊น?
ํ์ฌ ๊ธฐ์ฌ๊ฐ ์ฌ๋ฌ๋ถ์ ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ์ง ๋ชปํ๋ ๊ฒฝ์ฐ AI ์์ง์ ๋จธ์ ๋ฌ๋ ๋ถ์(์ค๋งํธ ๋ชจ๋ธ์ด ๋ฐฉ๊ธ ๋ง๋ค์ด์ ธ ๋ถ์ ํํ ๊ฒฝ์ฐ๊ฐ ์์ ์ ์์)์ ํตํด ๊ฐ์ฅ ์ ์ฌํ ๊ธฐ์ฌ๋ฅผ ์ถ์ฒํฉ๋๋ค:
๋ค์ํ ์ธ์ด์ JSONJSON์ Javascript ํ๊ธฐ๋ฒ์ ์ฌ์ฉํ์ฌ ๋ฐ์ดํฐ ๊ตฌ์กฐ๋ฅผ ๋ ์ด์์ํ๋ ๋ฐ์ดํฐ ํ์์ ๋๋ค. ๊ทธ๋ฌ๋ Javascript๊ฐ ์ฝ๋์์ ์ด๋ฌํ ๊ตฌ์กฐ๋ฅผ ๋ํ๋ผ ์ ์๋ ์ ์ผํ ์ธ์ด๋ ์๋๋๋ค. ์ ๋ ์ผ๋ฐ์ ์ผ๋ก '๊ฐ์ฒด'{}...
ํ ์คํธ๋ฅผ ์์ ๋กญ๊ฒ ๊ณต์ ํ๊ฑฐ๋ ๋ณต์ฌํ ์ ์์ต๋๋ค.ํ์ง๋ง ์ด ๋ฌธ์์ URL์ ์ฐธ์กฐ URL๋ก ๋จ๊ฒจ ๋์ญ์์ค.
CC BY-SA 2.5, CC BY-SA 3.0 ๋ฐ CC BY-SA 4.0์ ๋ฐ๋ผ ๋ผ์ด์ผ์ค๊ฐ ๋ถ์ฌ๋ฉ๋๋ค.
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค