1463 : 1로만들기

이문제는 정말 경의롭다

1부터 더해나가면 문제를 해결하는데 쉽게 접근 할 수있다.

1은 답이 당연히 1이고.

2는 1에 1을 더한것과 2로나눠지기때문에 2를 나눈 1에 1을 더한것
min(arr[1]+1, arr[2/2]+1)

3은 2에 1을 더한것과 3으로 나눠지기때문에 3을 나눈 1에 1을 더한것

min(arr[2]+1, arr[3/3]+1)

이런식으로 답을 가져가면 N 까지 했을때

arr[N] 에 있는것이 해답이 될것이다.

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

vector<int> DP;

int main(){

    int N;

    cin >> N;

    DP.assign(N+1, 0);

    for (int i = 2; i <= N; 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);

    }

    cout << DP[N] << endl;

    return 0;

}

Read More

1149번 -RGB 거리

본 문제는 DP(동적계획법) 을 사용해서 풀 수 있는 가장 쉬운 문제이다.

다음 그림 과 같이 다음 칸에는 같은색을 동일하게 칠할 수 없다.

예를 들어 N 의 녹색으로 갈수 있는것은 N-1 의 빨강색과 파란색이다.

이 경우는 N의 모든색이 마찬가지 이다.

하지만 내가 구하고 싶은값의 N 까지 선택해서 왔을때 가장 최소의 비용이 드는 것이다.

따라서 N의 빨강색 은 N-1 의 초록, 파랑중 최솟값, 녹색은 N-1 의 빨강색과 파랑색 중 의

최솟값, N 의 파랑색은 N-1 의 빨강색과 초록색 중의 최솟 값과 더해진 값이 될껏이다.

이렇게해서 0 부터 ~ N 까지 했을때 N번째에는 각자 의 색마다 최소의 값을 갖는 합을

가지고 있을 것이다. 따라서 ,  N번째 중에 가장 작은 값을 출력하면 답이다.

V 배열
R	G	B
26	40	83
49	60	57
13	89	99
DP 배열
R	G	B
26	40	83
40+49	26+60	26+57
26+57+13	26+57+89	26+60+99
Ans 26+57+13

다음 과 같이 됨을 알수 있다. 아래는 소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<iostream> #include<algorithm> #include<vector> using namespace std; vector<vector<int> > V; int main(){     int N;     int M;     int A=0;     vector<vector<int> > DP;     DP.assign(1001, vector<int>(3));     cin >> N;     V.assign(N+1, vector<int>(3, 0));     for (int i = 0; i < N; i++){         generate(V[i].begin(), V[i].end(), []()->int{int a; cin >> a; return a; });     }         DP[0] = V[0];           for (int i = 1; i <= N; i++){         for (int j = 0; j < 3; j++){             DP[i][j] = min(DP[i - 1][(j + 1) % 3], DP[i - 1][(j + 2) % 3]) + V[i][j];         }     }     cout << *min_element(DP[N].begin(), DP[N].end())<<endl;           return 0; }

Read More