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

문제 설명주어진 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배열은 누적합 배..

문제 설명행렬 곱셈의 연산 횟수는 곱셈 순서에 따라 달라진다. 행렬 N개의 크기가 주어졌을 때, 최적의 곱셈 순서를 찾아 최소 연산 횟수를 계산하는 문제이다.  이 문제는 2차원 동적 테이블을 이용해 풀면 되는 동적 계획법 문제이다. dp[i][j]는 행렬 i부터 j까지 곱하는데 필요한 최소 연산 횟수로 정의하자.-우선 dp[i][j]를 큰 값으로 초기화한다.-대각선 dp[i][i]는 자기 자신과의 곱셈이므로 0으로 초기화한다. 2차원 for문을 이용해 모든 경우의 범위를 탐색한다.이때 탐색범위의 시작점을 's', 끝점을 'e'라 하자.이때 k를 이용해 s~e까지를 탐색하며 s~e의 범위를 분할한다.(k = 분할지점)이때 dp[s][e]는 dp[s][k] + dp[k + 1][e] + (r[s] * c[..

문제 설명사건의 개수와 사건 간의 전후 관계가 주어진다. 이때 주어진 전후 관계를 바탕으로 다른 사건들 간의 전후 관계를 유추할 수 있는지 확인해야한다. 예측할 수 있는지 여부를 확인해 각각의 쿼리에 대해 답한다.  이 문제는 플로이드-워셜 알고리즘을 사용하는것이 편하다.(처음에 BFS로 풀어보려다 실패해 슬펐다)모든 사건 쌍에 대해 전후 관계를 효율적으로 계산할 수 있기 때문이다.그래프를 주어진 정방향으로 하나, 역방향으로 하나 총 2개를 만들어 이를 통해 사건의 전후관계를 파악할 수 있다.각각 주어진 쿼리에 대해 시작점과 끝점이정방향 그래프에서 이어져 있다면 "-1"역방향 그래프에서 이어져있다면 "1"둘다 이어져있지 않다면 "0"을 출력한다.소스 코드#include #include using name..