๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/Programmers

[C++/PGS] Lv.3 : ๋“ฑ๊ตฃ๊ธธ (DP)

728x90

๋™์  ๊ณ„ํš๋ฒ• (Dynamic Programming) : ๋“ฑ๊ตฃ๊ธธ

๋ฌธ์ œ ์ถœ์ฒ˜ - ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ๊ณ ๋“์  Kit

 

๋ฌธ์ œ ์„ค๋ช…

๊ณ„์†๋˜๋Š” ํญ์šฐ๋กœ ์ผ๋ถ€ ์ง€์—ญ์ด ๋ฌผ์— ์ž ๊ฒผ์Šต๋‹ˆ๋‹ค. ๋ฌผ์— ์ž ๊ธฐ์ง€ ์•Š์€ ์ง€์—ญ์„ ํ†ตํ•ด ํ•™๊ต๋ฅผ ๊ฐ€๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐ€๋Š” ๊ธธ์€ m x n ํฌ๊ธฐ์˜ ๊ฒฉ์ž๋ชจ์–‘์œผ๋กœ ๋‚˜ํƒ€๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์•„๋ž˜ ๊ทธ๋ฆผ์€ m = 4, n = 3 ์ธ ๊ฒฝ์šฐ์ž…๋‹ˆ๋‹ค.

๊ฐ€์žฅ ์™ผ์ชฝ ์œ„, ์ฆ‰ ์ง‘์ด ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (1, 1)๋กœ ๋‚˜ํƒ€๋‚ด๊ณ  ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ์•„๋ž˜, ์ฆ‰ ํ•™๊ต๊ฐ€ ์žˆ๋Š” ๊ณณ์˜ ์ขŒํ‘œ๋Š” (m, n)์œผ๋กœ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.

๊ฒฉ์ž์˜ ํฌ๊ธฐ m, n๊ณผ ๋ฌผ์ด ์ž ๊ธด ์ง€์—ญ์˜ ์ขŒํ‘œ๋ฅผ ๋‹ด์€ 2์ฐจ์› ๋ฐฐ์—ด puddles์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์˜ค๋ฅธ์ชฝ๊ณผ ์•„๋ž˜์ชฝ์œผ๋กœ๋งŒ ์›€์ง์—ฌ ์ง‘์—์„œ ํ•™๊ต๊นŒ์ง€ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋‹จ๊ฒฝ๋กœ์˜ ๊ฐœ์ˆ˜๋ฅผ 1,000,000,007๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

 

์ œํ•œ์‚ฌํ•ญ
  • ๊ฒฉ์ž์˜ ํฌ๊ธฐ m, n์€ 1 ์ด์ƒ 100 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
    • m๊ณผ n์ด ๋ชจ๋‘ 1์ธ ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.
  • ๋ฌผ์— ์ž ๊ธด ์ง€์—ญ์€ 0๊ฐœ ์ด์ƒ 10๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ์ง‘๊ณผ ํ•™๊ต๊ฐ€ ๋ฌผ์— ์ž ๊ธด ๊ฒฝ์šฐ๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง€์ง€ ์•Š์Šต๋‹ˆ๋‹ค.


 

์–ด์ฉ์ง€ ๋ฌธ์ œ๊ฐ€ x,y ์ขŒํ‘œ๋„ ๊ฑฐ๊พธ๋กœ ๋˜์–ด์žˆ๊ณ  ๋‚˜๋จธ์ง€๋ฅผ ๊ตฌํ•˜๋ผ๋Š” ๊ทธ๋Ÿฐ ๋”๋Ÿฝ๊ณ  ๋ณต์žกํ•œ ๋ฌธ์ œ์˜€๋Š”๋ฐ,

์•…๋ช… ๋†’๊ธฐ๋กœ ์œ ๋ช…ํ•œ ๋ฌธ์ œ์˜€๋‹ค.

 

์งˆ๋ฌธ ๊ฒŒ์‹œํŒ์— ์š•์ด ์กฐ๊ธˆ ๋งŽ์€.^^

 

๊ทผ๋ฐ ์ง„์งœ ๊ทธ๋Ÿด๋งŒํ•จ

๋‚œ ๋ฐ”๋กœ ์•Œ์•„์ฑ„๊ธด ํ–ˆ๋Š”๋ฐ ์ขŒํ‘œ x,y ๋ฐ˜๋Œ€์ธ๊ฑฐ ๋ชฐ๋ž๋˜ ์‚ฌ๋žŒ๋“ค์€ ํ•œ์ฐธ ์‚ฝ์งˆํ•˜๋‹ค๊ฐ€ ํ’€์—ˆ์„ํ…Œ๊ณ 

๋ง‰์ƒ ํ’€์–ด์„œ ์ •๋‹ต์€ ๋งž์•„๋„, ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ์—์„œ 0์ ์ด ๋‚˜์™€์„œ ํ—ค๋งจ ์‚ฌ๋žŒ๋“ค๋„ ๋งŽ๋‹ค

๋‹น์‹ ๋งŒ ๊ทธ๋žฌ๋˜๊ฒŒ ์•„๋‹ˆ๋‹ˆ ์•ˆ์‹ฌํ•˜์„ธ์š”! ๋ผ๋Š” ์˜๋ฏธ์ž…๋‹ˆ๋‹ค

 

๋‚˜๋„ ํšจ์œจ์„ฑ ๋•Œ๋ฌธ์— ํ†ต๊ณผ๋ฅผ ๋ชปํ–ˆ์—ˆ๋Š”๋ฐ, ์ผ๋‹จ ๋ฌด์กฐ๊ฑด dp๋กœ ํ’€์–ด์•ผ ํ•˜๊ณ  (์ •ํ™•ํžˆ๋Š” ๋ชจ๋ฆ„)

dp๊ฐ’์„ ๊ตฌํ•  ๋•Œ ๋งˆ๋‹ค % 1000000007๋ฅผ ํ•ด์ฃผ๋ฉด ํ†ต๊ณผํ•˜๋”๋ผ..ใ…Žใ…Ž

 

์กฐ๊ฑด ๋”ฐ์งˆ๊ฒŒ ๋งŽ์•„์„œ ๊นŒ๋‹ค๋กœ์› ๋‹ค.

 

1. (1,1)์€ ํ•ญ์ƒ 1์ด๋‹ค.

2.(1,y) ์€ ์œ„์ชฝ ๊ฐ’ ๊ทธ๋Œ€๋กœ, (x,1)์€ ์™ผ์ชฝ ๊ฐ’์„ ๊ทธ๋Œ€๋กœ ๊ฐ€์ ธ์™€์•ผ ํ•จ. ์ด๊ฑฐ ์ œ๋Œ€๋กœ ์ฒ˜๋ฆฌ ์•ˆํ•˜๋ฉด (1,2)(2,1)์— ๋ฌผ์›…๋ฉ์ด๊ฐ€ ์žˆ์„ ๋•Œ ์›๋ž˜ ๋‹ต์€ 0์ด ๋‚˜์™€์•ผ ํ•˜์ง€๋งŒ,  ๋‹ค๋ฅธ ๊ฒฐ๊ณผ๊ฐ’์ด ๋‚˜์˜ค๋Š” ๋ถˆ์ƒ์‚ฌ๊ฐ€ ์ƒ๊ธด๋‹ค

3. ์šฐ๋ฆฌ PS ์ƒ์‹์œผ๋กœ๋Š” (n,m)์ด ํ–‰๊ณผ ์—ด์ด๊ธฐ ๋•Œ๋ฌธ์—... ์ด ๋ฌธ์ œ์—์„œ๋Š” (m,n)์œผ๋กœ ํ’€์–ด์•ผํ•จ 

4. ๊ธฐ๋ณธ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๊ฐ€ ๊ตฌ๋ ค์„œ ์งˆ๋ฌธํ•˜๊ธฐ ๊ฒŒ์‹œํŒ์—์„œ ์ถ”๊ฐ€๋กœ ์ฐพ์•„๋ณด๋Š”๊ฑฐ ์ถ”์ฒœ

 

์—ฌ๋Ÿฌ๊ฐ€์ง€๋กœ ๋‡Œ์ ˆ ๋ฌธ์ œ์˜€๋‹ค;;

 

 

 

 

๋‚˜์˜ ํ’€์ด

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    int answer = 0;
    int dp[102][102]={{0,}};
    dp[0][0] = 1;
    dp[1][1] = 1; dp[1][2] = 1; dp[2][1] = 1;
    
    for(int i=0; i<puddles.size(); ++i){
        dp[puddles[i][0]][puddles[i][1]] = -1;
    }
    
    for(int j=1; j<=m; ++j){
        for(int i=1; i<=n; ++i){
            if(i==1&&j==1) continue;
            if(dp[j][i]==-1){ 
                dp[j][i] = 0; 
                continue; 
            }
            if(i==1){
                dp[j][i] = dp[j-1][i];
                continue;
            }
            if(j==1){
                dp[j][i] = dp[j][i-1];
                continue;
            }
            dp[j][i] = (dp[j-1][i] + dp[j][i-1])% 1000000007;
        }
        cout<<"\n";
    }
    answer = dp[m][n];
    return answer;
}

 

728x90