피너클의 it공부방

11280번: 2-SAT - 3https://www.acmicpc.net/problem/11280 SCC를 이용해서 풀었다. (P ∧ ¬Q) ¬P ∨ Q (A ∧ B) 이거는 A and B 이거다.(A ∨ B) 이거는 A or B 이거다.문제는 (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) ∧ (A ∨ B) 이런 식으로 나온다.즉 (A ∨ B) 이게 무조건 True 여야한다. 이제 (A ∨ B) 이걸 (¬A → B) ∧ (¬B → A) 이렇게 바꿔야 한다.그러기 위해서는 먼저 A → B 이게 뭔지를 알아야 한다. A → B 이건 조건문이다. "A 이면 B이다" 이런식으로 가는 것이다.A가 "비가 온다" B가 "우산을 쓴다" 이렇게 가고A가 True고 B가 True면"비가온다" 그러니 "우산을 쓴다" ..

4008번: 특공대https://www.acmicpc.net/problem/4008 dp와 Convex Hull Trick 으로 풀었다. 먼저 dp 식을 만들었다.dp[i] = 0 ~ i까지 특공대를 조직했을때 최대 전투력대충 이정도로 생각해보자. dp[i]를 만들었다고 생각하고 dp[i + 1]로 넘어가자dp[i + 1]은 dp[i]에서 새로운 병사가 추가되어 x[i + 1]이 추가되어야 한다.dp[i + 1] = dp[i] + a * x[i + 1] ^ 2 + b * x[i + 1] + c 하지만 새로 추가될 병사인 x[i + 1]은 앞의 인원과 그룹이 될수도 있다.x[i + 1]과 x[i]이 하나의 특공대가 되게 하려면 dp[i]가 아닌 dp[i - 1]을 사용해야한다.dp[i + 1] = dp[i..

13263번: 나무 자르기Convex Hull Trick 으로 풀었다. 문제를 먼저 봐보자.만약 내가 5번 나무의 높이를 0으로 만들면 5번 보다 번호가 큰 나무를 자르기 전까지는전기톱을 충전할때 b[5]만큼의 비용이 든다. dp[i]는 i번째 나무를 높이가 1이 될때까지 자르는데 필요한 충전 비용의 최소값으로 정의할 것이다.만약에 전기톱을 충전하는 비용이 100이라고 하고 나무의 높이를 10이라고 해보자.우리는 나무를 자르고, 충전한다.높이 10 | 충전 비용 0높이 9 | 충전비용 100높이 8 | 충전비용 200높이 7 | 충전비용 300높이 6 | 충전비용 400높이 5 | 충전비용 500높이 4 | 충전비용 600높이 3 | 충전비용 700높이 2 | 충전비용 800..

https://www.acmicpc.net/problem/2295 투포인터로 풀었다.int n;unordered_map visited;int arr[1001];int sum[1000001];int len = 0;선언 변수들이다. n = 1000 이므로 삼중 반복문을 돌리면 시간이 1000 ^ 3이 되어버려 제한시간안에 끝내지 못한다.그렇기에 이전에 arr에서 합을 따로 하나 구해놓을 것이다. 그것이 sum이다.visited는 sum안에 겹치는 숫자가 들어가지 않게 해준다.len은 sum의 길이다.  cin >> n; for (int i = 0; i > arr[i]; } sort(arr, arr + n);값들을 입력받은뒤 정렬해준다. 반드시 정렬해줘야햔다. for (int..

https://www.acmicpc.net/problem/7785그냥 set을 이용해 구현하는 문제다.#include #include #include using namespace std;int n;set s;string a, b;int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i > a >> b; if (b == "enter") { s.insert(a); } else { s.erase(a); } } set::reverse_iterator iter; for (iter = s.rbegin(); iter != s.rend(); iter++) { cout 전체코드다. 들어와야 나갈수 있..

https://www.acmicpc.net/problem/9506 수학문제다.int n;bool b[50001];int arr[50001];int len;n은 입력받는 숫자이고b는 약수인지 아닌지 기록하는 bool배열arr은 약수가 담기는 배열, len은 arr의 길이다. while (true) { cin >> n; if (n == -1) break; for (int i = 2; i 미리 세팅을 해둔다.for (int i = 2; i n/2까지만 반복문을 돌리며 만약 n이 i로 완전히 나누어떨어지고 약수로 체크가 되지 않았다면i와 n를 i로 나눈 수를 기록해주고 arr에 둘다 기록해준뒤 sum에 더해준다.arr[len] = 1;len += 1;sort(arr, arr + len);반복문에서 나오면 ..

https://www.acmicpc.net/problem/32684 그냥 구현문제다.#include using namespace std;double co, ek;int main(){ int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f; co = a * 13 + b * 7 + c * 5 + d * 3 + e * 3 + f * 2; cin >> a >> b >> c >> d >> e >> f; ek = a * 13 + b * 7 + c * 5 + d * 3 + e * 3 + f * 2 + 1.5; if (co > ek) cout

https://www.acmicpc.net/problem/11005구현문제다. 10진수로 64823이 있다라 해보자. 우리는 이걸 어떻게 10진수로서 보고있을까64823을 10으로 나눴을때 나머지는 3이다. 그럼 6482가 남는다.6482를 10으로 나눴을때 나머지는 2이다. 그럼 648이 남는다.648를 10으로 나눴을때 나머지는 8이다. 그럼 64이 남는다.64를 10으로 나눴을때 나머지는 4이다. 그럼 6이 남는다.6를 10으로 나눴을때 나머지는 6이다. 그럼 0이 남는다. 우리는 이렇게 보고있다.예제를 봐보자 60466175 이 숫자를 36으로 나눴을때 나머지는 35이다. 그럼 1679615이 남는다.1679615 이 숫자를 36으로 나눴을때 나머지는 35이다. 그럼 46655이 남는다.이를 반복..

https://www.acmicpc.net/problem/2745구현문제다. 진법을 어떻게 변화시키냐 이게 문제인데 이진수와 십진수를 예로 들어보자이진수 10101 이 있다고 했을때 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 인 것은 알것이다. 십진수 56473 이 있다고 했을때는5 * 10^4 + 6  * 10^3 + 4  * 10^2 + 7  * 10^1 + 3  * 10^0 인것도 알것이다. 그럼 예제에 나온 ZZZZ는 어떻게 해야할까?Z가 35라고 나왔으니 위에와 똑같이 만들면1 * 35^3 + 1 * 35^2 + 1 * 35^1 + 1 * 35^0 이다. 이를 코드로 짜면 된다.string n;int b;long long sum = 0;n과 b는 입력받..

https://www.acmicpc.net/problem/26042 queue를 이용한 구현문제다.int n;queue q;int a, b;int m = 0, l = 987654321;a, b는 입력받는 정보고m은 최대 학생수이고l은 최대 학생일때 번호 가장 작은 학생이다. cin >> n; while (n-- > 0) { cin >> a;값을 입력받고 if (a == 1) { cin >> b; q.push(b); if (q.size() > m) { m = q.size(); l = b; } else if (q.size() == m) { if (l > b) l = b; } }1을 입력받으면 다시 학생 번호 (b) 를 입력받는다.q에 b를 넣고만약 q의 크기가 m보..