제 12회 총장배 서강대학교 프로그래밍 대회 Champion (Ongoing)

 A. 순서쌍의 곱의 합

  단순 for 두번 O(N^2)으로는 시간초과가 나버린다.

  구하는 것은 

(A1*A2 + A1*A3 + ... + A1*AN) + (A2*A3 + A2*A4 + ... A2*AN) + ... + (AN-1*AN) 꼴이 된다.

  규칙성을 말하자면 A1의 경우 A2부터 AN까지의 합에 곱셈을 해야하고,

  AK의 경우(1<= K< N) AK+1부터 AN까지의 합에 곱을 해야한다.

  따라서 O(N)으로 해결 가능하다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

#include <cstdio> int main() {     long long S = 0,R=0;     int N, i,D,A[100001];     scanf("%d", &N);     for (i = 0; i < N; i++) {         scanf("%d", &A[i]);         S += A[i];     }     for (i = 0; i < N; i++) {         S -= A[i];         R += S*A[i];     }     printf("%lld", R);     return 0; }

 

 B. 로봇

  음.. 설명할게 없다. 그냥 문제 내용에 있는 것 그대로 구현을 한다.

  단지 방향성에 대해서 잘 처리해주면 코드를 다소 깔끔하게 작성할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <cstdio> int main() {     int R, C, dy[] = { -1,1,0,0 }, dx[] = { 0,0,-1,1 },ty,tx,y,x,k,seq[4],sp=0,chk[4],i;//상하좌우     bool vi[1000][1000] = {}, moved;     scanf("%d%d%d", &R, &C, &k);     while (k--) {         scanf("%d%d", &y, &x);         vi[y][x] = 1;     }     scanf("%d%d", &y, &x);     for (i = 0; i < 4; i++) {         scanf("%d", &seq[i]);         seq[i] -= 1;     }     vi[y][x] = 1;     while (1) {         for (i = 0; i < 4; i++) chk[i] = 0;         while (1) {             ty = y + dy[seq[sp]], tx = x + dx[seq[sp]];             if (0 <= ty && ty < R && 0 <= tx && tx < C && !vi[ty][tx]) {                 y = ty, x = tx;                 vi[y][x] = 1;             }             else break;         }         moved = 0;         for (i = 0; i < 4; i++) {             ty = y + dy[seq[i]], tx = x + dx[seq[i]];             if (0 <= ty && ty < R && 0 <= tx && tx < C && !vi[ty][tx])                 moved = 1;         }         if (!moved) break;         sp = (sp + 1) % 4;     }     printf("%d %d", y, x);     return 0; }

 C. 개업 2

  한 번에 요리 가능한 방법은 두 가지가 있다.

1. 하나의 웍만 이용한다.

2. 두 개의 웍을 이용한다.

  그 다음 N에 대해서 차곡차곡 계산해나가는 방식을 이용한다. dp[k] = dp[k-한번에 요리 가능한 수] + 1로 점화식을 세우고 계산을 해준다. 시간 복잡도는 O(N^2)

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

>#include <cstdio> #include <unordered_set> using namespace std; int min_v(int a, int b) { return a < b ? a : b; } int main() {     int N,M,*dp,*s,i,j,off;     scanf("%d%d", &N, &M);     dp = new int[N + 1]{};     s = new int[M];     unordered_set<int> ables;     for (i = 0; i < M; i++) {         scanf("%d", &s[i]);         ables.insert(s[i]);         if(s[i] <= N) dp[s[i]] = 1;         for(j=0;j<i;j++)             if (s[i] + s[j] <= N) {                 dp[s[i] + s[j]] = 1;                 ables.insert(s[i] + s[j]);             }     }       for (i = 1; i <= N; i++)         if (!dp[i]) {             dp[i] = 1e9;             for (auto it = ables.begin(); it != ables.end(); it++) {                 off = *it;                 if (1 <= i - off && dp[i - off] != 0)                     dp[i] = min_v(dp[i], dp[i - off] + 1);             }         }     printf("%d", dp[N] != 1e9 ? dp[N] : -1);     return 0; }

 D. 출근

  제 12회 총장배 서강대학교 프로그래밍 대회 Master 참고

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

#include <cstdio> #include <queue> using namespace std; int min_v(int a, int b) { return a < b ? a : b; } struct _d { int y, x; }; int main() {     bool board[1000][1000];     int R, C, N, *dy, *dx, i, j, vi[1000][1000] = {};     scanf("%d%d", &R, &C);     for (i = 0; i < R; i++) for (j = 0; j < C; j++)         scanf("%d", &board[i][j]);     scanf("%d", &N);     dy = new int[N], dx = new int[N];     for (i = 0; i < N; i++)         scanf("%d%d", &dy[i], &dx[i]);     queue<_d> q;     for (j = 0; j < C; j++)         if (board[0][j]) {             q.push(_d{ 0,j });             vi[0][j] = 1;         }     while (!q.empty()) {         _d u = q.front(); q.pop();         for (i = 0; i < N; i++) {             int ty = u.y + dy[i], tx = u.x + dx[i];             if (0 <= ty && ty < R && 0 <= tx && tx < C && board[ty][tx] && !vi[ty][tx]) {                 vi[ty][tx] = vi[u.y][u.x] + 1;                 q.push(_d{ ty,tx });             }         }     }     int ans = 1e9;     for (j = 0; j < C; j++)         ans = min_v(ans, vi[R - 1][j] == 0 ? 1e9 : vi[R - 1][j]);     printf("%d", ans == 1e9 ? -1 : ans - 1);     return 0; }

 E. 과제

  제 12회 총장배 서강대학교 프로그래밍 대회 Master 참고

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <cstdio> #include <algorithm> #include <queue> using namespace std;   int main() {     int n, i, ans = 0;     pair<int, int> a[1000];     scanf("%d", &n);     for (i = 0; i < n; i++) scanf("%d%d", &a[i].first, &a[i].second);     sort(a, a + n);     priority_queue<int> pq;     for (i = 0; i < n; i++) {         ans += a[i].second;         pq.push(-a[i].second);         if (pq.size() > a[i].first) ans += pq.top(), pq.pop();     }     printf("%d", ans);     return 0; }

 F. 세부

  첨에는 Maximum flow줄 알았다. 하지만 구하는 것은 단 한번 최대의 크기다.

  해보진 않았지만 이분탐색으로 풀 수 있는 문제긴 하다. BOJ 1939 중량제한 문제와 같다.

  하지만 나는 BFS + dp문제로 변형해서 해결했다.

  모든 방문점을 0으로 초기화시키고, BFS의 시작점은 INF로 두고, 각 방문점에 대해서 가능한 용량의 max값을 취해준다.

  dp[k] = k까지 갈 때, k로 가져갈 수 있는 금빼빼로의 최대 개수.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <cstdio> #include <vector> #include <queue> using namespace std; struct _d { int v, w; }; vector<vector<_d>> adj; int min_v(int a, int b) { return a < b ? a : b; } int main() {     int N, M, s, t, u, v, w,*dp;     scanf("%d%d%d%d", &N, &M, &s, &t);     dp = new int[N] {};     s--, t--;     adj.resize(N);      while (M--) {         scanf("%d%d%d", &u, &v, &w);         u--, v--;         adj[u].push_back(_d{ v,w });         adj[v].push_back(_d{ u,w });     }     queue<int> q;     dp[s] = 1e9, q.push(s);     while (!q.empty()) {         u = q.front(), q.pop();         for (_d& e : adj[u])             if (dp[e.v] < min_v(dp[u], e.w)) {                 dp[e.v] = min_v(dp[u], e.w);                 q.push(e.v);             }     }     printf("%d", dp[t]);     return 0; }

 G. 대문자

  솔루션을 참고했다.

  문자열의 길이를 L이라고 할 때, 끝부터 참고해서 dp를 구성한다. dp[k] = k번째 문자부터 L까지의 가능한 대문자 문자열 수

  

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

#include <cstdio> #include <cstring> const int MOD = 1000000007; int main() {     char S[1001];     int dp[1001] = {}, L,i ,j,chk[26];     scanf("%s", S);     L = strlen(S);     for (i = L; i >= 0; i--) {         memset(chk, 0, sizeof(chk));         dp[i] = 1;         for (j = i; j < L; j++) {             if (++chk[S[j] - 'a'] == 3) {                 dp[i] += dp[j + 1];                 dp[i] %= MOD;             }         }     }     printf("%d", (dp[0] + MOD - 1) % MOD);     return 0; }

  H. 세금

?

1