오늘 올림피아드 2차 대회를 치르고 왔습니다.
실력 부족,,, 으로 두문제 풀고 남은 두문제 섭테만 긁다 왔네요
문제는 :
정보올림피아드
한국정보올림피아드(KOI) 공식 홈페이지. 시험 요강, 접수 안내.
koi.or.kr
1. 타일 교체 tile
간단한 문제입니다. k가 0이나 1이라 k가 0이면 dfs한번 돌려주면 되는거고
k가 1이면 n^2번 돌면서 각 좌표를 다른 타일로 교체해주면서 dfs돌면 됩니다
시간복잡도는 O(n^4) 정도? n이 50이라 할만해요
2. 괄호 bracket
생각보다 쉬운 문제였습니다. vector<string> dp[N]선언해주시고
dp테이블 만들어서 돌리시면 됩니다.
dp[i] = min( k = 1 to i-1 dp[i-k]+dp[k])
if(i%2==0) dp[i]=min(dp[i],"("+dp[i/2]+")")
if(i%3==0) dp[i]=min(dp[i],"{"+dp[i/3]+"}")
if(i%5==0) dp[i]=min(dp[i],"["+dp[i/5]+"]")
3. 검은 돌 stones
옜날 koi 문제에서 본 듯 한데.. 까먹어서 섭테만 긁었습니다
->https://www.acmicpc.net/problem/2584 이문제 풀이와 유사하네요
노드마나 a[n][b] 테이블을 들고 서브트리에서 만들어질 수 있는 (n,b) 경우의 수를 모두 가지고있다가 부모노드한테 넘겨서 다시 그 부모노드의 자식의 a테이블을 합쳐가면서 부모한테 넘기고.. 반복하시면 됩니다.
시간복잡도는 O(n^3logn)이어서 섭테 2번까지밖에 못받았네요
4. 고압선 powerline
음.. 아이디어문제 아닌가싶네요 결국 섭테만 긁었지만...
중학교때 배우는 점과 직선 사이의 거리를 이용해봅니다. 직선의 방향벡터u만 알면 각 점을 지나고 벡터u를 따르는 직선들을 알 수 있고 그 직선들 간의 거리를 알 수 있습니다.
이 직선들 간의 거리의 최댓값이 p라고 하죠.
그럼 모든 직선들의 p값중 최댓갑의 절반이 답입니다.
그럼 직선의 방향벡터는 어떻게 구할까요?
두 가지 경우가 있습니다.
1. 두 점을 지나는 직선
2. 두 점 정중앙을 지나고 두 점을 지나느 직선에 수직인 직선
이것들만 구해서 위에 말씀드린대로 p값들 구하고 그 중 최댓값을 구해서 반으로 나눈값을 출력하시면 됩니다!
시간복잡도는 O(n^3logn)이라 섭테 2번까지밖에 못받았네요.....(데자뷰가..?)
뭔가 더 해보면 섭테 3긁을 수 있을것 같았는데 실패했어요..
느낀점
이번이 마지막 정올인데 정작 성과가 없어서 슬퍼요..흑..
작년보다 점수를 더 받긴 했는데, 뭐 다들 잘하셨겠죠.
확실히 실력 부족을 느끼게 되었고 백준이나 코포에서 더 노력하고 다른 블로그 참고하며 더 공부해야된다는걸 새삼 느꼈습니다. 솔루션 적은게 두서없고 올솔브도 아니라 부끄럽지만, 나중에라도 더 잘할 수 있도록 노력할겁니다!!