출처https://www.acmicpc.net/problem/15724처음엔 주지수라길래 무술 중에 하나인 주짓수인줄 알고 주짓수랑 알고리즘을 어떻게 연관지을까 궁금했지만 단순히 땅에 사는 사람들의 합을 구하는 문제였다..풀이 전략누적합을 구하는 문제이므로 처음에는 직접 구해야 하는 사각형의 범위를 지정해서 범위 내의 모든 cell값을 전부 더하는 방식을 시도했다. 하지만, 뒤에서 얘기하겠지만 이렇게 하게 될 경우 시간 초과 문제가 발생하기 때문에 DP를 활용해서 풀이할 것이다.풀이이 문제의 예시를 그려보면 위의 그림과 같다. DP로 누적합을 구하는 알고리즘의 경우 형태만 알아놓으면 정말 쉽게 풀 수 있다.Main code를 보면,for (int i=1; i이게 누적합을 구하는 알고리즘인데, 해석을 해보..

출처https://www.acmicpc.net/problem/9251풀이 전략'알고리즘및문제해결기법' 수업에서 Dynamic Programming [A.K.A DP]에 대해 배우면서 예시로 배웠던 LCS [Longest Common Sequences, 최장부분공통수열] 알고리즘을 사용하여 문제를 풀 것이다.이 문제를 풀기 위해서는 점화식을 알아야 하고, 점화식을 잘 모른다면 표를 그릴줄만 알아도 점화식 유도는 충분히 할 수 있을 것이라고 생각한다.풀이사실 LCS 알고리즘은 왠만한 코딩테스트 준비용 서적에 거의 다 나와있을 정도로 코딩테스트에도 자주 빈출되고, 그만큼 유명한 알고리즘이기 때문에 점화식을 외워놓는다면 쉽게 풀 수 있을 것이다.위의 그림에서 표를 해석하면, i=0, j=0인 부분 (파란색 형광..

출처https://www.acmicpc.net/problem/2293풀이 전략동전의 합을 만족하는 경우의 수를 구하는 문제이다. 다른 알고리즘으로도 풀 수 있겠지만, 중복을 허용하지 않는다는 점과 동전의 금액이 그때그때 입력 받는다는점이 DP로 해야하는 이유라고 생각해서 DP로 풀이를 하였다.풀이먼저, 1원만 있을 때 만족하는 경우의 수와 2원이 추가되었을 때의 경우의 수를 보면 2원이 추가되었을 때 특징이 보이는데, 2의 배수인 2, 4, 6, 8, 10에서 경우의 수가 1씩 증가한다는 점이다. 그러나 이것 만으로 점화식을 구하면 틀릴 가능성이 존재하기 때문에 5원을 추가했을 때의 경우의 수도 구해보았다.5원을 추가했을 때를 보면 4원까지는 2원을 추가했을 때의 경우의 수와 동일하다가 5원을 추가했을 ..

출처https://www.acmicpc.net/problem/2565풀이 전략처음엔 입력 받은 a,b 쌍을 b를 기준으로 정렬해서 시작점(a)의 크기를 비교해서 DP 값을 올려주는 방식으로 구현하려고 했으나, 그렇게 해보려고 했더니 여러가지 경우의 수가 존재하게 되어 복잡해진다는 단점이 존재했다. 그래서 a를 정렬해서 b의 크기를 비교해서 그걸 기준으로 구하는 방식으로 구하였다.풀이처음 시도한 풀이는 파란색 줄로 b를 정렬해서 풀려는 전략이였었는데, 이렇게 하게 될 경우 1-8, 3-9는 확정적으로 제거해야 하지만, 이 둘을 제거하고 난 뒤, 4-1과 2-2가 겹치기 때문에 2가지 경우의 수가 존재하게 된다. 어차피 최솟값을 찾는 문제이기 때문에 값은 두 경우의 수 모두 똑같이 나오게 되긴 하겠지만, 번..

출처https://www.acmicpc.net/problem/13699풀이 전략문제에서 주어진 대로 점화식을 그대로 구현하기만 하면 된다.점화식이 조합에서 파스칼삼각형처럼 대칭을 이루고 있으므로 하나는 왼쪽에서, 다른 하나는 오른쪽에서 움직이면서 F[n]에 저장해놓으면 된다.소스 코드#include #include using namespace std;long long ignition(int n){ long long F[n+1]; F[0]=1; for(int i=1;i>N; long long result=ignition(N); cout결과