pinevienna blog

A 전봇대와 B 전봇대에 연결된 전깃줄이 서로 교차되지 않도록 전깃줄을 제거할 때, 제거해야 하는 전깃줄의 최솟값을 구하는 문제 전깃줄이 교차되려면 i번째 전깃줄이 그 위/밑의 전깃줄보다 더 위로/밑으로 가야한다는 점을 이용하면 된다 → B전봇대와 연결되는 A전봇대의 위치가 정렬되어 있을 때, 아래 그림과 같이 B전봇대의 가장 긴 수열만 전깃줄을 교차하지 않고 이을 수 있다 가장 긴 수열을 구하고 전깃줄 개수에서 수열의 길이를 빼버리면 제거해야 할 전깃줄의 개수가 나온다 물론 vector 등을 사용하여 A, B를 함께 입력받은 상태여야 함 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 28 29 30 31 32 33 34 ..

가장 긴 바이토닉 부분 수열을 찾는 문제 앞에서 증가 + 뒤에서 증가하는 수열을 합쳐서 가장 길면 된다 dp 배열을 두개 만들어서 앞뒤로 증가하는 부분수열의 길이를 저장하고, 두 배열의 값을 주소별로 더한 max 값이 가장 긴 바이토닉 부분 수열이 된다 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 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, input[1001] = { 0, }, arr[1001] = { 0, }, ar..

입력된 배열에서 숫자를 무작위로 두 개 뽑아 더했을 때 나올 수 있는 모든 수를 중복 없이 벡터에 넣어 return 하는 문제 합은 이중 for문으로 모두 더하면 됨 bool형 배열을 만들어서 더할 때마다 값이 있는지 없는지 체크해줬다 없는 값이 나왔으면 answer에 push 해주면 된다 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 #include #include #include using namespace std; vector solution(vector numbers) { vector answer; bool b[201] = { false, }; int sum; for (int i = 1; i

같은 인형을 연속으로 두 개 뽑으면 터지는데, 몇 개의 인형이 터지는지 구하는 문제 stack 만들어주고 뽑은 숫자(인형)와 stack.top을 비교하여 같으면 answer+=2, 다르면 push하면 된다 같아서 터졌으면 pop해줘야 하고, 터뜨리든 push하든 인형을 뽑은 거니까 board에 0을 넣어줘야 한다 0 안넣어서 틀림ㅎㅎ ^_^.. 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 28 29 30 #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; stack s; int cur..

2+1 행사를 하는 곳에서 유제품을 살 때 최소비용을 구하는 문제 비싼 제품을 할인 받고, 싼 제품을 할인 없이 사는게 이득이다 내림차순으로 정렬하여 위치가 %3==0인 수들만 계산에서 제외시키면 끝 12345678910111213141516171819202122232425262728#include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, c, res = 0; vector v; cin >> n; v.push_back(100001); //정렬했을 때 제일 앞에 위치 for (int i = 0; i > c; v.push_back(c); } sort(v.begin(), v..