FandPROG FandPROG

각 사람까지의 거리의 합이 최소가 되는 우체국의 위치를 구해야 하는 문제이다.오늘 재체점에 갑자기 틀렸습니다. 가 떠서 급히 다시 푼 문제이다. 우체국이 설치될 위치는 전체 인구의 중앙이 되는 지점입니다. 이는 총 인구의 절반 지점에 해당하는 위치를 의미한다. 즉, 인구의 합을 2로 나눈 값에 해당하는 누적 인구를 찾아서 그 위치를 결정하면 된다. #include #include #include using namespace std;using ll = long long;int n;vector > vec;int main() { int i, j; scanf("%d", &n); ll ans = 0; for(i=0;i= res) { printf("%d", vec[i].fi..

최대한 많은 팀을 만들되, 각 팀의 능력치 합이 최소값 M 이상이 되도록하는 문제이다. 투 포인터를 이용하면 간단하게 풀린다.로직은 다음과 같다.두 개의 포인터 low와 high를 사용하여 배열의 양 끝에서부터 탐색을 시작한다. - low 포인터는 배열의 시작에서, high 포인터는 배열의 끝에서 시작한다. - 현재 low와 high가 가리키는 두 원소의 합이 m 이상이면, 해당 팀을 구성할 수 있으므로 팀의 수를 증가시키고 포인터를 이동시킨다. - 현재 합이 m 미만이면, low 포인터를 오른쪽으로 이동시켜 합을 증가시킬 기회를 만든다. - 이 과정을 low 포인터가 high 포인터와 같아지거나 넘을 때까지 반복한다. #include #include using namespace std;int n, m;..

주어진 전구묶음을 배열해 가장 인접한 두 전구의 상태가 다른 부분이 가장적도록 하는 문제이다.주어지는 전구묶음의 수가 10이하로 적음으로 O(N!)의 풀이를 생각할 수 있다. 먼저 주어진 전구의 묶음안에서 인접한 두 전구의 상태가 다른 부분이 몇개인지 찾는다. 그 후 1~N으로 순열을 만들어 해당 idx를 갖는 전구의 묶음을 순서대로 배열한다.이때 묶음과 묶음 경계에 있는 두 전구의 상태만 비교해주면된다. (각 묶음 안에 있는 인접한 상태가다른 전구는 이미 처리했기 때문) 즉 백트래킹을 이용하여 쉽게 풀 수 있는 문제이다. #include #include #include #include using namespace std;int n;string s[10];int ch[10];int ans = 2e9;ve..

주어진 정수 N을 1, 2, 3의 합으로 나타내는 경우의수를 구하는 문제이다. 단, 합은 대칭을 이루어야 한다. DP 문제는 의외로 간단하다. 양쪽을 1, 2, 3으로 감싸는 방식을 생각하면 편하다. 예를 들어 dp[8]을 구할 때는 1 + 6을 구하는 방법 + 1, 2 + 4를 구하는 방법 + 2, 3 + 2를 구하는 방법 + 3으로 접근할 수 있다. 이를 바탕으로 점화식은 dp[i] = dp[i - 2] + dp[i - 4] + dp[i - 6]으로 세울 수 있다. 이 방식으로 문제를 해결할 수 있지만, 초기값을 6까지 설정해야 해서 다소 번거로울 수 있다. #include #include #include using namespace std;#define MOD 1000000009;int dp[100..

유사코문제셋으로 공부를 해본다해본다 하다가 드디어 처음으로 문제를 풀어보았다. 처음이니 가볍게 브론즈부터 시작해야지 라고 생각했는데 내 실력을 너무 과대 평가한것같다. 생각보다 엄청 어려웠다. 체감상 난이도는 Farmer John Actually Farms 못풀겠어서 중간에 에디토리얼을 봤다. A : Candy Cane Feast 구현자체는 쉽지만 시간복잡도때문에 쉽게 손이 가지않는 문제다. 하지만 나이브하게 처리해도 시간안에 돌아간다는 사실을 증명한다면 구현은 어렵지않다. 나이브한 방법에서는 O(N * M) 시간이 소요될 수 있으며, 이는 최대 4 * 10^10의 연산량으로 시간 초과가 발생할 수 있다. 따라서 이를 해결하기 위한 시간 최적화 방법을 고려해야 한다. 1. 각 소의 앞에 있는 소들이 자신..

본격적으로 PS공부를 하기로 하고, 첫 CP여서인지 어려웠다.대회 당시에 A, B, C 문제는 쉽게 풀었다. A는 솔브닥 기준으로 브론즈 5 수준의 쉬운 문제였고, B도 브론즈 1 정도의 난이도였다. C는 문제를 처음엔 잘 이해하지 못했지만, 나이브하게 풀어도 풀렸다. 체감 난이도로는 실버 중위권 정도인 것 같다.> A 소스더보기#include int main(){ int a, b; scanf("%d %d", &a, &b); if(a == 1 && b == 0) printf("Yes"); else if(a == 0 && b == 1) printf("No"); else printf("Invalid"); return 0;}> B 소스더보기#include #include usi..

문제 설명주어진 M×N 크기의 보드에서 K×K 크기의 체스판을 만들려고 한다. 체스판의 색상은 두 가지 패턴 중 하나를 따라야 하며, 검은색과 흰색이 번갈아야 한다. 주어진 보드에서 K×K 체스판을 잘라낸 후, 최소한으로 다시 칠해야 하는 정사각형의 수를 계산하는 문제이다, 이 문제는 백준의 "단계별 - 누적합" 단계에 속해있는 문제이다. 하지만 이런 형식의 문제를 처음 본다면 이 문제를 어떻게 누적합으로 풀어야할지 잘 모르겠는 경우가 있을 것이다. 어쨋든 이 문제는 2차원 누적합의 응용을 통해 풀 수 있다. 우선 sum[i][j] = "(1, 1) ~ (i, j)정사각형에서 Bst(반복되는 완성된 패턴을 미리 저장해둔 배열)과 map(입력된 배열)의 다른 패턴의 수"라 정의하자. 생각을 하다보면, 체스..

문제 설명각 장이 저장된 파일들을 하나의 파일로 합치는 과정에서, 두 파일을 합칠 때 발생하는 비용이 두 파일 크기의 합으로 주어진다. 이때, 모든 파일을 하나로 합치는 데 필요한 최소 비용을 계산하는 문제이다. dp[i][j]: 배열 arr의 i번째 파일부터 j번째 파일까지를 합치는 데 필요한 최소 비용이라 정의한다. 2중 for문을 이용해 모든 구간을 검사한다. 이때 구간의 시작을 "s", 끝을 "e"라 하자.m변수를 잡아 s~e 구간을 분할해 준다.(m = 분할지점) -이때 dp[s][e]는 dp[s][m] + dp[m + 1][e] + sum[e] - sum[s - 1]을 통해 갱신해준다. 구간 [s, e]를 두 부분으로 나누어 합치는 데 필요한 비용을 의미한다.이때 필요한 sum배열은 누적합 배..