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 <=...

Read More

1149번 -RGB 거리

본 문제는 DP(동적계획법) 을 사용해서 풀 수 있는 가장 쉬운 문제이다. 다음 그림 과 같이 다음 칸에는 같은색을 동일하게 칠할 수 없다. 예를 들어 N 의 녹색으로 갈수 있는것은 N-1 의 빨강색과 파란색이다. 이 경우는 N의 모든색이 마찬가지 이다. 하지만 내가 구하고 싶은값의 N 까지 선택해서 왔을때 가장 최소의 비용이 드는 것이다. 따라서 N의 빨강색 은 N-1 의 초록, 파랑중 최솟값, 녹색은 N-1 의 빨강색과 파랑색 중 의 최솟값, N 의 파랑색은 N-1 의 빨강색과 초록색 중의 최솟 값과 더해진 값이 될껏이다. 이렇게해서 0 부터 ~ N 까지 했을때 N번째에는 각자 의 색마다 최소의 값을 갖는 합을 가지고 있을 것이다. 따라서 ,  N번째 중에 가장 작은 값을 출력하면 답이다. V 배열 RGB 264083 496057 138999 DP 배열 RGB 264083 40+4926+6026+57 26+57+1326+57+8926+60+99 Ans...

Read More