λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

πŸ“ μ•Œκ³ λ¦¬μ¦˜/BOJ

[C++/BOJ] 2169 : λ‘œλ΄‡ μ‘°μ’…ν•˜κΈ° (DP)

728x90

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];
}

 

728x90