https://www.acmicpc.net/problem/2169
λ¬Έμ
NASAμμλ νμ± νμ¬λ₯Ό μν΄ νμ±μ 무μ μ‘°μ’ λ‘λ΄μ 보λλ€. μ€μ νμ±μ λͺ¨μ΅μ κ΅μ₯ν 볡μ‘νμ§λ§, λ‘λ΄μ λ©λͺ¨λ¦¬κ° μΌλ§ μ λκΈ° λλ¬Έμ μ§νμ N×M λ°°μ΄λ‘ λ¨μν νμ¬ μκ°νκΈ°λ‘ νλ€.
μ§νμ κ³ μ μ°¨μ νΉμ±μ, λ‘λ΄μ μμ§μΌ λ λ°°μ΄μμ μΌμͺ½, μ€λ₯Έμͺ½, μλμͺ½μΌλ‘ μ΄λν μ μμ§λ§, μμͺ½μΌλ‘λ μ΄λν μ μλ€. λν ν λ² νμ¬ν μ§μ(λ°°μ΄μμ νλμ μΉΈ)μ νμ¬νμ§ μκΈ°λ‘ νλ€.
κ°κ°μ μ§μμ νμ¬ κ°μΉκ° μλλ°, λ‘λ΄μ λ°°μ΄μ μΌμͺ½ μ (1, 1)μμ μΆλ°μμΌ μ€λ₯Έμͺ½ μλ (N, M)μΌλ‘ 보λ΄λ €κ³ νλ€. μ΄λ, μμ 쑰건μ λ§μ‘±νλ©΄μ, νμ¬ν μ§μλ€μ κ°μΉμ ν©μ΄ μ΅λκ° λλλ‘ νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯
첫째 μ€μ N, M(1≤N, M≤1,000)μ΄ μ£Όμ΄μ§λ€. λ€μ Nκ°μ μ€μλ Mκ°μ μλ‘ λ°°μ΄μ΄ μ£Όμ΄μ§λ€. λ°°μ΄μ κ° μλ μ λκ°μ΄ 100μ λμ§ μλ μ μμ΄λ€. μ΄ κ°μ κ·Έ μ§μμ κ°μΉλ₯Ό λνλΈλ€.
λ°±μ€ κ³¨λ2 dpλ¬Έμ !
μμΉ«νλ©΄ κ·Έλν νμ λ¬Έμ λ‘ μ€ν΄ν μ μμ κ² κ°μλ€.
κ·Έλ¦¬κ³ 60νΌμΌνΈ μ λμμ νλ¦°λ€λ©΄ μλμ²λΌ μ μ²΄κ° μμμΈ ν μ€νΈμΌμ΄μ€λ₯Ό κ³ λ €ν΄λ³Ό κ²!
μ κ° κ·Έλ κ² νλ Έμ΄μ,,,
λ°λ³΅λ¬Έ λ리면μ dpλ₯Ό μ±μΈ λ, λ²μλ₯Ό μ μ€μ ν΄μΌ νλ€.
μ΄μ°¨μλ°°μ΄μ μΆλ ₯νλ©΄μ μ½λλ₯Ό μμ νλ©΄ λμμ΄ λλ€^-^
λμ νμ΄
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n;
int m;
int map[1001][1001];
int fromRight[1001];
int fromLeft[1001];
int dp[1001][1001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
cin >> map[i][j];
}
}
for (int j = 1; j <= m; ++j)
{ // 맨 μμ€
dp[1][j] += dp[1][j - 1] + map[1][j];
}
for (int i = 2; i <= n; ++i){
// μΌ vs μ
fromLeft[1] = dp[i - 1][1] + map[i][1];
fromRight[m] = dp[i - 1][m] + map[i][m];
for (int j = 2; j <= m; ++j){
fromLeft[j] = max(dp[i - 1][j], fromLeft[j - 1]) + map[i][j];
}
// μ€ vs μ
for (int j = m-1; j > 0; --j){
fromRight[j] = max(dp[i - 1][j], fromRight[j + 1])+ map[i][j];
}
// maxλ₯Ό dpμ μ μ₯
for (int j = 1; j <= m; ++j){
dp[i][j] = max(fromLeft[j], fromRight[j]);
}
}
// cout << "\n";
// for (int i = 0; i <= n+1; ++i){
// for (int j = 0; j <= m+1; ++j){
// cout << dp[i][j] << " ";
// }
// cout << "\n";
// }
cout << dp[n][m];
}
'π μκ³ λ¦¬μ¦ > BOJ' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[C++/BOJ] 2493 : ν (Stack) (0) | 2024.11.17 |
---|---|
[C++/BOJ] 11660 : κ΅¬κ° ν© κ΅¬νκΈ° 5 (DP) (0) | 2024.11.17 |
[C++/BOJ] 2644 : μ΄μκ³μ° (λ€μ΅μ€νΈλΌ) (0) | 2023.05.18 |
[C++/BOJ] 1325 : ν¨μ¨μ μΈ ν΄νΉ (BFS/DFS) (1) | 2023.05.14 |
[C++/BOJ] 1012 : μ κΈ°λ λ°°μΆ (BFS/DFS) (0) | 2023.05.12 |