dldyou

우하단 / 좌하단 대각선 누적합을 각각 진행해주고, (x, y)에서 변의 길이가 k인 형태에서의 아름다운 정도를 구해서 답을 갱신해주면 된다. $O(N^3)$으로 해결 가능하다.int N, A[MAXN][MAXN], B[MAXN][MAXN];int main(void) { fastio; cin >> N; for (int i = 1; i > A[i][j]; B[i][j] += B[i - 1][j + 1] + A[i][j]; // B 좌하단 대각선 누적합 A[i][j] += A[i - 1][j - 1]; // A 우하단 대각선 누적합 } } int ans = -INF; for (int i = 1; i

1. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다.2. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다.3. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. 위 조건에 따라 그대로 구현해주면 되는 시뮬레이션 문제이다. 최근에 나온 과제를 먼저 해야하므로 스택을 사용해서 구현해주자. int N;stack> s;int main(void) { fastio; cin >> N; int score = 0; for (int i = 1; i > isExist; if (isExist) { // 해당 시간에 과제가 존재 cin >> A >> T; s..

수열 $S$에서 $K$개의 원소를 임의로 삭제하였을 때, 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다. 수열에서 필요한 정보는 홀짝이니, $S[i] = S[i]\ \&\ 1$로 홀수면 1, 짝수면 0으로 $S$를 초기화해주자. 일정 범위에서 범위를 늘리면 포함되는 홀수, 짝수는 같거나 증가한다. 줄이면 같거나 감소한다. 나머지는 투포인터를 이용하여 개수를 세어주면 된다. int N, K, S[MAXN]; int main(void) { fastio; cin >> N >> K; for (int i = 1; i > S[i], S[i] = (S[i] & 1); int s = 1, e = 1; int cnt = S[1], ans = !S[1], tmp = !S[1]; while (s

https://www.acmicpc.net/problem/22858 22858번: 원상 복구 (small) $P_1, P_2, \cdots , P_N$의 수가 적혀 있는 $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 수열 $D_1, D_2, \cdots , D_i , \cdots , D_N$이 있다. 이때 각 $i$에 대해 $D_i$번째 카드를 $i$번째로 가져오는 www.acmicpc.net 규칙에 따라 섞인 수열의 맨 처음 형태를 구하면 된다. $P_i$에서 $i=D_i$인 경우 $S_i$가 된다. 즉, $P[D[i]]=S[i]$이다. 이를 $K$번 반복해주면 된다. $NK\leq 10^7$이기에 전부 돌려봐도 해결 가능하다. int N, K, S[MAXN], D[MAXN], P[MAX..

3개의 제품을 한 번에 사면 그 중 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 된다. 만약, 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 한다. 이때, 최소비용으로 모든 제품을 구입하면 된다. 결국, 무료로 지불하는 금액을 최대화하면 최소비용으로 모든 제품을 구입하는 것과 같다. 최대화하려면 비싼 순서대로 무료로 구입하면 된다. 하지만 3개를 묶어서 그 중 가장 싼 제품만 무료로 구입할 수 있기에, 비싼 순서대로 나열했을 때 3의 배수에 속해있는 것을 제외한 모든 제품의 가격을 더해주면 된다. 반대로 생각하면 모든 가격에서 3의 배수에 속해있는 가격을 제외하면 된다. long long N, C[MAXN], ans; int main(void) { fastio;..

돌 $N$개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람이 누구인지를 구하여라. 게임은 상근이가 먼저 시작한다. 돌이 1, 3, 4개인 경우는 상근이가 돌을 1개 가져가면 상근이가 승리한다. 나머지도 채워보자. 2개인 경우는 1 - 1개 순서로 가져가 창영이가 승리한다. 5개인 경우는 3 - 1 - 1개 순서로 가져가 상근이가 승리한다. 6개인 경우는 4 - 1 - 1개 순서로 가져가 상근이가 승리한다. 7개인 경우는 1 - 4 - 1 - 1개 순서로 가져가 상근이가 승리한다. ... 이런 식으로 게임이 진행될 것이다. 6개인 경우에서 1개를..

각각의 작업마다 걸리는 시간이 다른 것을 $N$개를 모두 완료하기 위해 필요한 최소 시간을 구하는 문제이다. 작업들 사이에는 선행 관계가 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 하는 작업들이 있다. '선행 관계' 대놓고 위상 정렬 문제이다. 위상 정렬(topological sort)은 비순환 방향 그래프(DAG)에서 각 정점들이 가지는 위상에 따라 순서대로 나열하는 것을 의미한다. 선수 과목, 게임에서의 테크 등을 생각하면 편할 것이다. 각각의 건물이 지어지는 시간을 구한 다음 최댓값을 출력하면 그것이 모든 건물을 짓는데 걸리는 최소 시간이다. int N, cost[MAXN], in_degree[MAXN], dp[MAXN]; vector v[MAXN]; queue q; int main..

정수 $X$가 주어졌을 때, $X$와 구성이 같으면서 $X$보다 큰 수 중 가장 작은 수를 출력하는 문제이다. $X$는 최대 6자리 수이므로 나올 수 있는 수는 최대 $6!$개이다. 모두 탐색을 해도 충분한 시간이다. 맨 처음 수를 저장해놓고, 숫자를 정렬한다. 그 후에는 그 다음으로 나올 수열을 찾아보며 해당 수열이 맨 처음 수보다 큰지 확인을 해가면서 탐색을 진행하면 된다. 만약, 끝까지 큰 값이 없었다면(내림차순 정렬값이 맨 처음 수였다면) 0을 출력한다. string s; int n; bool vst[7]; void solve(string str) { if (str.length() == s.length()) { if (stoi(str) > n) { cout s; n = stoi(s); sort(a..

$N$개의 길이 중 3개를 선택하여 삼각형을 만들었을 때, 세 변의 길이의 합의 최댓값을 구하는 문제이다. 그리디하게 접근해 보자. 세 변의 길이의 합을 최대로 만들려면 당연히 길이들 중 최대한 긴 것을 선택해야 한다. 그렇다면 정렬을 먼저 해보자. 가장 큰 3개를 봤을 때, 삼각형이 안 되면 어떤 길이를 선택해야 할까? XXXXXXXOOO에서 XXXXXXOXOO 이런 식으로 선택을 해야 할까? 삼각형을 이루는 세 변의 길이의 조건을 생각해 보자. '가장 긴 변의 길이는 다른 두 변의 길이의 합보다 작아야 한다.' 가장 긴 3개를 골랐을 때, 삼각형이 안 된다면 가장 긴 길이를 유지한 채로 다른 변을 더 짧은 길이를 선택하는 것은 삼각형에서 멀어지는 길이다. 위의 상황과 같이 가장 긴 길이를 기준으로 바..

양의 정수로 이루어진 수열에서 '연속하는 부분 수열의 합이 $d$로 나누어 떨어지는 것'의 개수를 구하는 문제이다. 단순하게 생각해 보면 모든 구간에 대해 확인을 해보면 된다. 하지만 이는 $O(n^2)$이 걸리며, 문제에서 $n$의 제한은 $50\ 000$까지이다. 다른 방법을 생각해보자. 누적합을 이용해 볼 수 있을까? $A_i$부터 $A_j$까지의 합을 7로 나눈 나머지가 3이라고 하자. 그리고 $A_k$까지의 합을 7로 나눈 나머지를 4라고 하자. $(i\lt j\lt k)$ 그렇다면 $A_{j + 1}$부터 $A_k$까지의 합을 7로 나눈 나머지는 몇이 될까? 1이 될 것이다. $A\ mod\ M \equiv T_1$이고 $B\ mod\ M \equiv T_2$이면 $(A + B)\ mod\ M..