프로그래머스 - 동적 계획법(등굣길, 도둑질)

문제 링크 - https://programmers.co.kr/learn/courses/30/parts/12263

👀문제이해 및 풀이방법

어제에 이어서 dp문제들을 풀었다.. 3번은 무난하게 풀었고 4번은 힌트를 찾아보고 풀 수 있었다😢
다 예전에 한번씩은 봤던 유형인데 잘 안풀렸다 dp문제들을 한번씩 다시 봐야겠다
3번은 2차원 dp테이블을 만들고 이전 값들 더해주면서 경우의 수를 찾아나가면 된다. mod로 나머지 뽑아주는거 잊지않기
4번은 점화식까지는 생각해 냈는데 원형을 어떻게 체크해야할지 몰라서 찾아봤다 첫번째 값을 넣고 마지막값을 빼고 , 첫번째를 빼고 마지막을 빼는 방식으로 2번 dp를 돌렸는데
아무래도 for문으로 dp를 돌리는게 익숙치 않아서 생각해 내기가 힘들었다 백준문제들로 좀더 연습해볼예정이다

📝코드

1 등굣길

#include <string>
#include <vector>
using namespace std;
int mod=1000000007;
class routes{
private:
    vector<vector<int>> dp;
    int M,N;
public:
    routes(int m,int n,vector<vector<int>>& puddles):M(m),N(n){
        dp.resize(M,vector<int>(N,-1));
        dp[0][0]=1;
        for(vector<int> i : puddles)
            dp[i[0]-1][i[1]-1]=0;
    }
    int DP(int m,int n){
        if(dp[m][n]!=-1)
            return dp[m][n];

        if(m==0)
            dp[m][n]=DP(m,n-1);
        else if(n==0)
            dp[m][n]=DP(m-1,n);
        else
            dp[m][n]=(DP(m-1,n)+DP(m,n-1))%mod;
        return dp[m][n];
    }
    int find_sol(){
        return DP(M-1,N-1);
    }
};
int solution(int m, int n, vector<vector<int>> puddles) {
    routes rt(m,n,puddles);
    return rt.find_sol();
}

2 도둑질

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int solution(vector<int> money) {
    int answer;
    vector<int> dp(money.size());
    dp[0]=money[0];
    dp[1]=max(money[1],money[0]);
    for(int i=2;i<money.size()-1;i++)
        dp[i]= max(dp[i-2]+money[i],dp[i-1]);
    answer=dp[money.size()-2];
    dp[0]=0;
    dp[1]=money[1];
    for(int i=2;i<money.size();i++)
        dp[i]=max(dp[i-2]+money[i],dp[i-1]);

    return max(answer,dp[money.size()-1]);
}