동적계획법 고득점 kit 풀이 완료, 후기

코딩 테스트, 대회를 위해 대비해야 하는 필수 알고리즘중 하나이다.

동적계획법은 바로 해답을 구하는 것이 아니고, 이전에 계산했던 값을 활용하는 알고리즘이다.

동적계획법 문제는 대체로 코드가 짧지만 점화식을 세우기 어렵다는 특징이 있다.

백준에서 문제풀이를 제일 많이 했던 알고리즘인 만큼 레벨4(도둑질)에 해당하는 문제도 크게 어렵지 않게 풀었다.

프로그래머즈 문제들 뿐만 아니라 여러 동적계획법을 이용한 문제들도 포스팅 해두었으니 필요하면 참고해도 좋을 것이다.

 

모든 문제

[난이도 중상] 도둑질 kimcoder.tistory.com/92?category=879353

[난이도 중하] 등굣길 kimcoder.tistory.com/123?category=879353

[난이도 하] 정수 삼각형 kimcoder.tistory.com/55?category=879353 (백준 문제와 완전 일치해서 중복 포스팅하지 않음)

[난이도 중] N으로 표현 (테스트 케이스가 정확하지 않은 것으로 판단하여 공식적인 포스팅은 하지않고 소스코드를 첨부함)

-N으로 표현 소스 코드-

#include <vector>
using namespace std;
int mini(int a,int b){
    if(a>b) return b;
    else return a;
}
int answer = 11;
void dfs(int N, int number, int length, int sum){
    int newnum = 0;
    if(length>8) return;    
    if(sum == number) {
        answer = mini(answer, length);
    }
    for(int i=0; i<8; i++){
        newnum = newnum*10 + N;
        dfs(N, number, length+i+1, sum+newnum);
        dfs(N, number, length+i+1, sum-newnum);
        dfs(N, number, length+i+1, sum*newnum);
        dfs(N, number, length+i+1, sum/newnum);
    }
}
int solution(int N, int number) {
    dfs(N, number, 0, 0);
    if(answer>8) return -1;
    return answer;
}