A - Superhero Transformation
단순 구현
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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <iostream> using namespace std; char s[1001]; char t[1001]; int main(void) { int i = 0, j = 0; char temp = 'a'; while (temp != '\n') { scanf("%c", &temp); s[i++] = temp; } temp = 'a'; while (temp != '\n') { scanf("%c", &temp); t[j++] = temp; } if (i != j) { printf("No\n"); return 0; } bool check = true; for (int k = 0; k < i; k++) { if (t[k] == 'a' || t[k] == 'e' || t[k] == 'i' || t[k] == 'o' || t[k] == 'u') { if (s[k] != 'a'&& s[k] != 'e' && s[k] != 'i' && s[k] != 'o' && s[k] != 'u') { check = false; break; } } else { if (s[k] != 'a'&& s[k] != 'e' && s[k] != 'i' && s[k] != 'o' && s[k] != 'u') continue; check = false; break; } } if (check) printf("Yes\n"); else printf("No\n"); return 0; } |
B. Average Superhero Gang Power - DP
대략적인 내용은 n명의 사람이 각각 자연수의 능력치를 가지고 있을때, 한번의 동작으로 능력치를 1을 올리거나 한 사람을 제거할 수 있다. 한 사람에 대해서는 최대 k번 능력치를 올릴 수 있으며, 동작은 총 m번까지만 할 수 있다. 이때, 전체 인원의 평균능력치의 최댓값을 찾는 문제였다.
고안한 방식은 제일 작은 능력치를 가진 사람을 한명씩 제거하는 과정을 거치는 방식이다.
즉, 제거할 인원수가 결정이 되고나면, 최대값은 유일하게 결정된다.
이러한 성질을 바탕으로 다음과 같은 점화식을 세웠다.
D[i] : i명을 제거 했을때 최대값
어떤 수의 인원이 제거될때, 최대값이 되기 위해서는 제거된 대상들이 가장 작은 능력치를 가지고 있어야한다.
가령, 5, 3, 2, 1, 5라는 능력치를 가진 인원중 한명을 제거한다면, 가장 낮은 능력치인 1를 가진 사람을 제거해야 한다.
이를 위해선 초기에 데이터를 입력받고 정렬하면 매 단계에서 가장 낮은 능력치를 가진 사람을 지울때 쉽게 접근할 수 있다.
이러한 식을 세우고 나면, 다음과 같은 식이 정의된다.
A[k] = k 번째로 낮은 능력치를 가진 사람의 능력치
Sn = A[0] + A[1] + ... + A[n]
D[0] = Sn + min(nk , m) / n
한명도 제거 하지 않은 상태에서의 최댓값은 Sn에서, n명의 사람들을 각각 k만큼의 능력치를 올려주는 경우와 m번의 연산 횟수중 최솟 값을 더해주면 된다.
D[i] = (S[n] - S[i] + min((n - i )*k, m - i )) / (n - i);
결국 위와 같은 식이 정의가 된다.
이 문제에서 주의할 점은 bottom up 시에 i<n 과 i<=m 의 조건을 함께 걸어줘야 문제가 생기지 않는다.
i<=m이 없다면, 지우는 동작을 연산횟수를 초과하여 수행한 결과도 포함되기 때문에, 결과 값이 바뀔 수 있기 때문이다.
또한, 마지막으로 문제에서 출력 precision에 대한 조건이 있다.
이 떄문에 cout.precision(30)으로 지정하여 출력하고 문제를 해결하였다.
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 38 39 40 41 42 | #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(30); double n, k, m; cin >> n >>k >> m; vector<double> A(n + 1); vector<double> D(n + 1); vector<double> S(n + 1); double sum = 0; for (int i = 1; i <= n; i++) cin >> A[i]; sort(A.begin(), A.end()); for (int i = 1; i <= n; i++) S[i]=S[i-1]+A[i]; D[0] = (S[n] + min(n*k, m))/n; double max =D[0]; for (int i = 1; i < n && i<=m; i++) { D[i] = (S[n] - S[i] + min((n - i )*k, m - i )) / (n - i); if (D[i] > max) max = D[i]; } cout << max; return 0; } |
C. Creative Snap
세그먼트 트리를 활용해서 푸는 문제였다. 생각은 났지만 구현을 하다 코드가 계속 꼬여서 결국 풀지 못했었다.
