프로그래머스 - 동적 계획법(N으로 표현, 정수 삼각형)

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

👀문제이해 및 풀이방법

동적 계획법 문제 2개 오늘은 dp문제를 풀어봣는데 너무 오랜만에 풀어서 그런지 문제가어려운건지.. 생각이 잘 안났다.
결국 2문제밖에 못풀어서 2문제씩 나누어서 올려야겠다
첫번 째 문제 N으로 표현 일단 그냥 숫자를 던져줘도 어떻게 구해야 할지 감도 안잡혔다.. 이전 값을 어떤 값으로 잡아서 저장해 놔야할지도 모르겟고 한참을 고민했었던것 같다 결국 힌트? 를 보았고 몇번째인 지를 생각해도 다음번째랑 어떤 연관이 있을지를 생각했다
set을 사용해서 무작정 for문으로 풀었는데 마음에 들지 않는다 나중에 다시 생각해서 dp의 형태로 풀어보도록 해봐야겠다
2번문제는 이게 dp문제인가 싶은 느낌이였다 prefixsum느낌으로 그냥 한번씩 쭉 가면서 큰거를 더해주면서 내려갔다 새로운 자료구조를 쓸 일이 없었다
내일은 3 4 번 마저 풀어봐야지👊

📝코드

1 N으로 표현

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
typedef long long ll;
int solution(int N, int number) {
    unordered_set<int> S[8];
    string Nstr ="";
    string str = to_string(N);
    for(int i=0;i<8;i++){
        Nstr+=str;
        S[i].insert(stoi(Nstr));
        for(int j=0;j<i;j++){
            for(auto s1 : S[j]){
                for(auto s2 : S[i-j-1]){
                    S[i].insert(s1+s2);
                    S[i].insert(s1*s2);
                    S[i].insert(s1-s2);
                    if(s2)
                        S[i].insert(s1/s2);
                }
            }
        }
        if(S[i].find(number)!=S[i].end())
            return i+1;
    }
    return -1;
}

2 정수 삼각형

#include <string>
#include <vector>
using namespace std;
int solution(vector<vector<int>> triangle) {
    int answer = triangle[0][0];
    for(int i=1;i<triangle.size();i++){
        for(int j=0;j<triangle[i].size();j++){
            if(!j)
                triangle[i][j]=triangle[i-1][j]+triangle[i][j];
            else if(j == triangle[i].size()-1)  
                triangle[i][j]=triangle[i-1][j-1]+triangle[i][j];
            else
                triangle[i][j]=max(triangle[i-1][j-1],triangle[i-1][j])+triangle[i][j];
            answer=max(answer,triangle[i][j]);
        }
    }


    return answer;
}