A더보기출력해야 하는 문자열 규칙:$N$이 짝수인 경우:문자열의 중앙에 두 개의 '=' 기호가 위치하며, 그 좌우에 '-' 기호가 배치됩니다.전체 '-' 기호의 개수는 $N-2$개이며, 좌우에 균등하게 분배됩니다.즉, 왼쪽에 $\frac{N-2}{2}$개의 '-'와 오른쪽에 $\frac{N-2}{2}$개의 '-'를 붙이고, 그 사이에 "=="를 넣습니다.$N$이 홀수인 경우:문자열의 중앙에 한 개의 '=' 기호가 위치하며, 그 좌우에 '-' 기호가 배치됩니다.전체 '-' 기호의 개수는 $N-1$개이며, 좌우에 균등하게 분배됩니다.즉, 왼쪽에 $\frac{N-1}{2}$개의 '-'와 오른쪽에 $\frac{N-1}{2}$개의 '-'를 붙이고, 그 사이에 "="를 넣습니다.문제:정수 $N$이 주어졌을 때, 아..
D더보기이 문제는 양의 정수 $N$이 주어질 때, 두 개의 양의 정수 $(x, y)$가 존재하여 $x^3 - y^3 = N$을 만족하는지 확인하는 문제이다. 존재하는 경우, 해당 $(x, y)$ 쌍을 출력하고, 존재하지 않는 경우 $-1$을 출력해야 한다. 가능한 여러 해 중 하나만 출력해도 된다.해설$x^3 - y^3 = N$에서 $x - y = d$라 두면 $x^3 - y^3 = d(x^2 + xy + y^2)$.$x^2 + xy + y^2 \geq (x - y)^2 = d^2$이므로 $d^3 \leq d(x^2 + xy + y^2) = N$,즉, $d \leq \sqrt[3]{N}$이다. 이제 $d$를 $1$부터 $\sqrt[3]{N}$까지 모두 탐색한다. $x = k + d, ; y = k$라 두..
$D$더보기이 문제는 $n$명의 고객이 크리스마스 트리를 구매하려고 할 때, 상점이 모든 트리에 대해 동일한 가격을 설정하여 최대 수익을 얻는 방법을 찾는 문제이다. 각 고객은 두 개의 가격 한계값 $a_i$와 $b_i$를 가지며, 가격이 $a_i$ 이하이면 긍정적인 리뷰를 남기고, $b_i$ 이하이면 부정적인 리뷰를 남긴 채 구매하며, $b_i$를 초과하면 구매하지 않는다. 상점은 최대 $k$개의 부정적인 리뷰를 허용하면서 최대 수익을 얻을 수 있는 트리의 가격을 결정해야 한다.간단한 에디토리얼이 문제는 고객별 가격 임계값 a와 b를 이용해, 하나의 가격을 설정했을 때 얻을 수 있는 총 수익을 계산하는 문제이다. 가능한 후보 가격은 a와 b의 집합에 한정되며, 스위프 라인 기법을 통해 이벤트를 처리하면..
#define fore(i, l, r) for(int i = int(l); i fore (i, 0, q) { char c; cin >> id[i] >> c; id[i]--; ch[i] = c == '+' ? 1 : -1; }0부터 q미만까지 입력받기fore (mask, 1, 1 > nxt) & 1) // 비트마스킹 할 때 1인지 확인하는 방법 기억해두기 continue; int nmask = mask | (1 비트마스킹 dp 순환const int INF = int(1e9);INF 전처리 위 내용보다는 문제를 해결하기 위한 풀이를 세우는 것이 중요하다.
수도 코드 과연 필요할까? - 12764번
머릿속으로 생각하고 노트로 끄적여도 도무지 정리가 안 돼서, 수도코드로 썼더니 시간은 좀 걸려도 확실하게 매듭지을 수 있었다. 만세! 깔끔한 수도코드는 아니지만, 틀린 부분도 있고전체적인 흐름은 노트에 적혀 있으니 머리에 비는 부분이 생겨서 코드를 완성할 수 있다. 문제였던 부분은 변수 타입을 어떻게 설정하고무엇을 정렬해야할지였다. 1번: 시작 시간에 어떤 변수에다가 집어 넣고 종료 시간이 되면 빼면 되겠다!2번: 근데 앞자리부터 채워야하네? pq 써서 항상 앞자리를 뽑을 수 있도록 하자두개가 keypoint이지 않을까. P가 0일 수도 있다는 점 주의하자.문제의 조건을 항상 정확하게 확인하도록 #include #define ft first#define sd second#define all(x) (x)...
이번 실수는 c++ 특, ll, int 실수했다.만약 논리는 맞는데 틀린다면 이 부분을 봐야겠지.2%에서 틀리길래 논리가 틀린건줄 알았다. 실버여도 방심하면 안되겠다풀 문제 많구만 바이너리 서치 하라는 문제다.O(M)이어도 시간초과라는 것에서부터 시작한다.잘 뚫어지게 쳐다보다 보면0부터 M까지 잘랐을 때 내림차순 정렬되어 있다는 것을 알 수 있다~정렬이 되어있으면 할만한 것 중 하나가 바이너리 서치. 다만, 바이너리 서치를 그동안 STL에서 뽑아 쓰기만 했다면이 문제에서 뒤통수 맞았을 것이다.나처럼. 꼭! 시간이 되지 않더라도, 남지 않더라도 구현해보자.언젠가 쓸 일이 오더라.under_bound와 upper_bound 까지 세세하게 구현해보자!#include #define ft first#define ..
요즘 자주 실수하는데0-based-index와 1-based-index일 때for문과 if문이 어떻게 다른지 각별히 주의하자 bfs와 dfs 연습하시고 문제는 연결 요소의 개념만 알고 있으면 된다.뭉텅이 하나를 연결 요소 하나라고 한다.연결 요소끼리는 끊어져있다.bfs/dfs를 이용해서 뭉텅이씩 bfs 돌리면 된다.#include using namespace std;int n, m;int ans = 0;vector graph[1001];bool visited[1001];void bfs(int start) { queue q; q.push(start); visited[start] = true; while (!q.empty()) { int tmp = q.front(); // ..
1 매크로#define 으로 말그대로 매크로다.덕분에 많이 쓰는 것들 간략하게 줄일 수 있다. 2 타입 별칭(alias) using 과 typedef 를 말한다. 차이는 링크에서!이건 타입에 관련해서 줄여쓸 수 있다. 3 참조자(reference)여러번 방문하는 배열이 있을 때 레퍼런스 변수를 하나 두면 깔끔하게 쓸 수 있다.특이점은 주소를 넘겨주기 때문에 변수를 수정해도 참조한 배열의 원소를 수정한다는 것.무엇보다 간지난다 c++ 고수가 된 느낌. 4 비트 연산자&는 해당 값이 1인지 확인할 때 쓰고|는 채울 때 쓴다. 5 누적곱과 전처리수의 길이가 50이 넘기 때문에 그냥은 구할 수 없다."50"은 충분히 표현할 수 있기에 50개의 배열에10씩 곱해가며 저장. 다만 이것도 ..