9518 로마 카톨릭 미사

9518 로마 카톨릭 미사 https://www.acmicpc.net/problem/9518

교회의 모든 사람은 인접한 8방향과의 사람과 악수를 한다.
상근이가 교회에 들어갔을 때 모든사람이 악수를 했을 때의 최댓값을 구하는 문제이다.

N이 작으므로 $O(N^4)$으로 풀 수도 있으나 $O(N^3)$의 풀이방법이 있다.
중복되게 악수하는 경우를 구하되 나중에 2로 나누면 상근이를 제외한 악수하는 경우의 수이고
앉아있는 사람들의 자리에서 인접한 빈자리로 악수할 수 있는 가장 빈번한 빈자리가 상근이가 앉으면 악수할 수 있는 최댓값이 되는 자리이다.

#include <cstdio> #include <algorithm> using namespace std; int N, M; char map[51][51]; int s[51][51]; int dy[] = { 1,0,0,-1,1, 1, -1 ,-1 }; int dx[] = { 0,-1,1,0,-1, 1, 1 ,-1 }; int main() {     scanf("%d%d", &N, &M);     for (int n = 0;n < N;n++) scanf("%s", &map[n]);       int ans = 0;     for (int n = 0;n < N;n++) {         for (int m = 0;m < M;m++) {             if (map[n][m] == 'o') {                 for (int i = 0;i < 8;i++) {                     int ny = n + dy[i], nx = m + dx[i];                     if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;                     if (map[ny][nx] == 'o') ans++;    //성당 사람들끼리 중복되게 악수 하는 경우                      else s[ny][nx]++;        //상근이가 앉는 최적 자리를 위해 누적                 }             }         }     }     int ret = 0;     for (int n = 0;n < N;n++) {         for (int m = 0;m < M;m++)             ret = max(ret, s[n][m]);             }     printf("%d\n", ans / 2 + ret);    //중복되게 악수하는경우 / 2, 상근이가 앉았을 때 악수하는 경우     return 0; } Colored by Color Scripter

cs

14653 너의 이름은

14654 너의 이름은 https://www.acmicpc.net/problem/14653

카카오 톡 방처럼 N개의 메세지에서 보낸사람과 읽지않은 사람 수가 주어진다.
Q번째 메세지를 읽지 않았을 가능성이 있는사람을 구하는 문제이다.

Q번째 메세지를 확실히 읽은 사람은 3가지 경우가 있다.
1. 문제에 제시된 'A'
2. Q번째 메세지 이후로 메세지를 보낸 사람들
3. Q번째 메세지의 읽지않은 사람 수와 같은 메세지를 보낸 사람들

#include <cstdio> #include <vector> using namespace std; int N, M, K; bool f[10001]; int message[10001][2]; int sum[27]; vector<char> ans; int main() {     scanf("%d%d%d", &N, &M, &K);       for (int m = 0;m < M;m++) {         char c;         scanf("%d %c", &message[m][0], &c);         message[m][1] = c - 'A';         sum[c - 'A']++;     }     for (int m = 0;m < M;m++)         if (message[m][0] == message[K - 1][0])             f[message[m][1]] = true;     for (int k = 0;k < K;k++) {         if (k == K - 1) {             for (int n = 0;n < N;n++) {                 if (!sum[n] && !f[n] && n != 0)                     ans.push_back(n + 'A');             }         }         sum[message[k][1]]--;     }     if (ans.empty() || message[K - 1][0] == 0) printf("-1\n");     else         for (auto n : ans) printf("%c ", n);       return 0; } Colored by Color Scripter

cs

codeground 최대 직사각형

Codeground 최대 직사각형 https://www.codeground.org/practice/practiceProblemView

2차원 배열이 주어질 때 부분배열의 원소들의 합이 가장 큰 것을 구하는 문제이다.

사실 $O(N^4)$ 방법 밖에 생각이 나지 않아 풀어서 AC를 받았으나 $O(N^3)$풀이가 존재한다.

행의 구간합을 구해놓고 greedy하게 풀어나가는 해법이다.

#include <cstdio> #define max(a,b) ((a)>(b)?(a):(b)) int main(){     setbuf(stdout, NULL);     int T;     scanf("%d", &T);          for (int t = 1; t <= T; t++){         int N;         int sum[101][101] = { 0 };         scanf("%d", &N);         for (int n = 1; n <= N; n++)             for (int m = 1; m <= N; m++){                 scanf("%d", &sum[n][m]);                 sum[n][m] += sum[n][m - 1];    //행의 구간합 구함             }         int ans = -999999999;         for (int n = 1; n <= N; n++){             for (int m = n; m <= N; m++){                 int s = 0;                 for (int k = 1; k <= N; k++){                     int plus;                     plus = sum[k][m] - sum[k][n - 1];    //n은 m,k가 반복될때 고정되있음                     s = max(s + plus, plus);        //행을 이어붙일 경우, 이어붙이지 않을 경우                     ans = max(ans, s);                 }             }         }         printf("Case #%d\n", t);         printf("%d\n", ans);     }     return 0; } Colored by Color Scripter

cs