[2025 1학기 알고리즘 스터디] 김민주 #2주차

알고리즘 스터디 2주차 : DP

 

1. 1로 만들기 

https://www.acmicpc.net/problem/1463 

 

 

---

💡문제 분석 및 알고리즘 설계

처음에는 2 or 3의 배수이면 무조건 나누기 먼저한 후에 -1을 해서 1을 만드는 방식으로만 구현했었는데,

10의 경우, " -1 => /3 => /3 " 의 순서대로 행하는 것이 최소 연산 횟수임을 알게 되었습니다.

 

따라서 두 방식으로 모두 계산하면서 그 중 최소값을 취하는 방식으로 설계하게 되었습니다.

 

 

 

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;
int n;
int DP[1000000];

void calc(int i){

    DP[i] = DP[i-1] + 1;
    if (i%2 == 0) {
        DP[i] = min(DP[i], DP[i/2] + 1);
    }
    if (i%3 == 0) {
        DP[i] = min(DP[i], DP[i/3] + 1);
    }

}

int main(){
    cin >> n;

    for (int i= 2; i <= n; i++) {
		calc(i);
	}

	cout << DP[n];

    
}

 

 

 

 

 

 

 

---

 

2. 계단 오르기 

https://www.acmicpc.net/problem/2579 

 

---

 

💡문제 분석 및 알고리즘 설계

 3연속으로 계단을 밟으면 안된다는 점이 가장 신경써야할 부분이었습니다.

계단을 최대한 많이 밟아서 점수를 획득해야하므로,

1, 2, 4번째 or 1, 3, 4번째를 모두 비교해서 둘 중 큰 값으로 결정하는 방식으로 구현했습니다.

 

 

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int num;
int st[301];
int pt[301];


int main(){
    cin >> n;
    for (int i=1; i<n+1; i++){
        cin >> st[i];
    }
    pt[1] = st[1];
    pt[2] = st[1] + st[2];
    pt[3] = max(st[1]+st[3], st[2]+st[3]);

    for (int i=4; i<n+1; i++){

        pt[i] = max(pt[i-3] + st[i-1] , pt[i-2]) + st[i];
    }
    cout << pt[n];
}

 

 

 

 

 

---

 

3. 가장 긴 증가하는 부분 수열 

https://www.acmicpc.net/problem/11053

 

 

 

---

 

💡문제 분석 및 알고리즘 설계

가장 긴 증가하는 부분 수열 문제들 중 가장 기본이 되는 문제입니다.

 

증가하는 경우에 포함시킬 수 있는 모든 경우에 대해 계산해서 DP에 저장하고,

가장 큰 값을 구하기위해 max_element를 사용했습니다.

 

 

 

 

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int N;
vector<int> A;
vector<int> B;
int num;

int longer(int id){
    for (int j=1; j<id; j++){
        if (A[id] > A[j])
            B[id] = max(B[id], B[j]+1);
    }
    return 0;
}

int main(){
    cin >> N;
    A.resize(N+1);
    B.resize(N+1, 1);
    for (int i=1; i<N+1; i++){
        cin >> A[i];
    }

    for (int j=1; j<N+1; j++){
        longer(j);
    }

    int ans = *max_element(B.begin(), B.end());
    cout << ans << endl;
}