프로그래머스 고득점 Kit 하루만에 뽀개기 - 7. 동적계획법(C++) 풀이

https://programmers.co.kr/learn/courses/30/parts/12263

프로그래머스

- java풀이와 C++풀이가 거의 차이점이 없어서 C++ 풀이로만 정리하였다

 

1. N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

- DP로 풀지 않고 완전탐색으로 풀었다. 문제에서 주어진 조건 N이 9 이하였기 때문에 4^9 = 2^18 = 26만밖에 안되었기 때문에, DP로만으로 풀게 할 의도로 출제했다면 N값을 15 이상으로 키워야 한다. 재귀적으로 연산횟수와 결과값을 구해나가면서 num과 같아진 경우 연산횟수를 저장한다.

using namespace std;

int ans = 9, n, num;

void go(int cnt, int res) {
    if(cnt > 8) return;
    if(res == num) {
        if(ans > cnt) ans = cnt;
        return;
    }
    
    int seq = 0;
    for(int i = 1; i <= 9 - cnt; ++i) {
        seq = seq * 10 + n;
        go(cnt + i, res + seq);
        go(cnt + i, res - seq);
        go(cnt + i, res * seq);
        go(cnt + i, res / seq);
    }
}

int solution(int N, int number) {
    n = N, num = number;
    go(0, 0);
    if(ans > 8) return -1;
    return ans;
}

 

2. 정수 삼각형

https://programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

- 탑다운, 바텀업 둘 다 구해보자. 문제에 따라 둘 중 쉬운 방식이 떠오를 때가 많다. 종종 탑다운 방식으로만 열심히 풀다보면 바텀업이 생각 안 날 때가 많다

// 바텀업
#include <algorithm>
#include <vector>
using namespace std;

int d[501][501];

int solution(vector<vector<int>> triangle) {
    int N = triangle.size();

    d[0][0] = triangle[0][0];
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (j == 0) {
                d[i][j] = d[i - 1][j] + triangle[i][j];
            } else if (j == i) {
                d[i][j] = d[i - 1][j - 1] + triangle[i][j];
            } else {
                d[i][j] = max(d[i - 1][j - 1], d[i - 1][j]) + triangle[i][j];
            }
        }
    }
    
    return *max_element(d[N-1], d[N-1] + N);
}

#include <vector>
#include <cstring>
using namespace std;

int d[501][501];

int go(int r, int c, vector<vector<int>>& t) {
    if(r == t.size() - 1) return t[r][c];
    
    int& ret = d[r][c];
    if(ret != -1) return ret;
    return ret = max(go(r + 1, c, t), go(r + 1, c + 1, t)) + t[r][c];
}

int solution(vector<vector<int>> triangle) {
    memset(d, -1, sizeof(d));
    return go(0, 0, triangle);
}

 

3. 등교길

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

- 이 문제도 바텀업, 탑다운 둘 다 연습해본다. 진행방향이 2방향으로 정해져있어서 쉬운 문제

#include <vector>
using namespace std;

int MOD = 1e9 + 7;
int d[101][101];

int solution(int m, int n, vector<vector<int>> puddles) {
    for(auto& pos : puddles) {
        int x = pos[0], y = pos[1];
        d[y][x] = -1;
    }
    
    d[1][1] = 1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(i == 1 && j == 1) continue;
            else if(d[i][j] == -1) d[i][j] = 0;
            else d[i][j] = (d[i][j-1] + d[i-1][j]) % MOD;
        }
    }
    
    return d[n][m];
}

#include <vector>
#include <cstring>
using namespace std;

int MOD = 1e9 + 7;
int d[101][101];
int N, M;

int go(int r, int c) {
    if(r == N && c == M) return 1;
    if(r > N || c > M || d[r][c] == -2) return 0;
    
    int& ret = d[r][c];
    if(ret != -1) return ret;
    return ret = (go(r+1, c) % MOD + go(r, c + 1) % MOD) % MOD;
}

int solution(int m, int n, vector<vector<int>> puddles) {
    N = n, M = m;
    memset(d, -1, sizeof(d));
    for(auto& pos : puddles) {
        int c = pos[0], r = pos[1];
        d[r][c] = -2;
    }
    
    return go(1, 1);
}

 

4. 도둑질

https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

- 첫 집을 터는 경우, 털지 않는 경우로 나눠서 점화식을 짜면 된다. 

#include <vector>
using namespace std;

int d[1000001], d2[1000001];

int solution(vector<int> money) {
    int N = money.size();
    
    d[0] = d[1] = money[0];
    d2[1] = money[1];
    
    for(int i = 2; i <= N; ++i) {
        d[i] = max(d[i - 2] + money[i], d[i - 1]);
    }
    for(int i = 2; i <= N; ++i) {
        d2[i] = max(d2[i - 2] + money[i], d2[i - 1]);
    }
    
    return max(d[N-2], d2[N - 1]);
}

 

- 프로그래머스 고득점 Kit 문제 중에 DP 유형이 좀 빈약한 것 같다.