공지사항
결론부터 말하자면 초반에 A, B 빠르게 풀고 D번에서 계속 시간초과 떠서 2문제 밖에 풀지 못했습니다...
나름 열심히 공부한다고 생각은 했는데 역시 아직은 터무니 없이 부족한 것 같습니다.
고수님들의 후기를 보니까 C와 D 모두 Union Find 자료구조를 사용하는 문제였습니다.
최근에 종만북을 잘 안 보게 되었는데 이렇게 된 이상 종만북에 시간을 많이 투자를 해야겠다고 생각이 들었습니다.
올해 ACM-ICPC 본선을 가는 것이 최종 목표이기 때문에 더 이상 게을리하면 안될 것 같습니다.
카카오 Code Festival 2018 예선은 총 6 문제였습니다.
난이도는 baactree님이 말씀하신대로 A<=B<D<C<E<<<<<<F인 것 같습니다.(http://baactree.tistory.com/49)
저는 A와 B 문제만 AC를 맞았기 때문에 A, B만 설명할 수 있을 것 같습니다.
C와 D 문제는 같은 학교 학우이신 ssangba55님이 잘 설명하신 포스팅이 있기 때문에 참고하시면 될 것 같습니다.(https://blog.naver.com/pasdfq/221332735719)
물론 baactree님의 블로그를 참고하셔도 됩니다.
A번 문제는 솔직히 그냥 주는 문제였기 때문에 별도의 주석을 달지는 않겠습니다.
#include <iostream>
using namespace std;
int A[100 + 1], B[64 + 1];
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0); //cin 실행속도 향상
int test_case;
cin >> test_case;
A[1] = 500;
for (int i = 2; i <= 3; i++)
A[i] = 300;
for (int i = 4; i <= 6; i++)
A[i] = 200;
for (int i = 7; i <= 10; i++)
A[i] = 50;
for (int i = 11; i <= 15; i++)
A[i] = 30;
for (int i = 16; i <= 21; i++)
A[i] = 10;
B[1] = 512;
for (int i = 2; i <= 3; i++)
B[i] = 256;
for (int i = 4; i <= 7; i++)
B[i] = 128;
for (int i = 8; i <= 15; i++)
B[i] = 64;
for (int i = 16; i <= 31; i++)
B[i] = 32;
for (int t = 0; t < test_case; t++)
{
int a, b;
cin >> a >> b;
cout << (A[a] + B[b]) * 10000 << "\n";
}
return 0;
}
B번 문제는 갑자기 표준편차가 나와서 당황했지만 문제에서 평균과 표준편차를 어떻게 구하는지 다 명시해주기 때문에 쉽게 풀 수 있는 문제였습니다.
인형이 연속된 K개의 인형이 아닌 연속된 K개 이상의 인형인 것이 문제의 핵심이였고 부동소수점 오차를 조심해야하는 문제였습니다.
브루트 포스(Brute Force) 방식으로 시간 복잡도 O(N^3) 코드로 쉽게 AC를 받을 수 있었습니다.
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX = 500;
const int INF = 987654321;
int N, K;
double result;
int people[MAX];
void calculate(int start, int end)
{
double sum = 0;
for (int i = start; i <= end; i++)
sum += people[i];
double m = sum / (end - start + 1); //평균
double temp = 0;
for (int i = start; i <= end; i++)
temp += (people[i] - m) * (people[i] - m); //표준 편차
result = min(result, sqrt(temp / (end - start + 1)));
}
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0); //cin 실행속도 향상
cin >> N >> K;
for (int i = 0; i < N; i++)
cin >> people[i];
result = INF;
//K개 이상
for (int i = 0; i < N - K + 1; i++)
for (int j = i + K - 1; j < N; j++)
calculate(i, j);
printf("%.11f\n", result);
return 0;
}