하라는 한국정보올림피아드는 안하고!

아무튼 세종정보올림피아드가 끝났으니 예선 후기글을 써보려 합니다.

후기

이게 예선이 맞나? 정말 가슴이 웅장해진다.....
세종과학예술영재고는 전설이다....
내가 알던 그 세과영이 맞나?
맞는거같다....

일단 제 닉은 HS7251이었고, OI순위기준 4등 먹었습니다.
분명 HS3830이 펜타곤형이겠지 흑흑흑흑흑

A. 삼각형 만들기

a, b, c 중 가장 큰 변을 a로 두고 a>b+c인지 체크하면 된다.

B. 합격자의 수는?

for문 돌리자....

C. 세종이를 찾아라

arr[i] == 'S' && arr[i+1] == 'J'

D. 시간 계산

시간을 분단위로 환산하고
처리해준뒤에 잘 나눠주면 된다.

E. 수의 개수

10으로 나눈 나머지가 3인지 체크하고
10으로 나눠서 자릿수를 하나씩 없앤다
그다음 map<int,int> 에 박아서 숫자 개수를 세주었다.

F. D-Day 계산

달이 같으면 날짜만 빼서 계산해주면 되고
달이 다르면
(해당 달 날짜 - 시작날짜) + 사이의 달 날짜들 + 끝나는날짜

G. 연락망

dfs를 돌려주면서
vis배열 초기화 없이 체크하고
방문한적이 없다면 1을 반환.
1의 갯수세기 문제가 된다

H. 도시락가게

하아니 이걸 왜 못풀죠(1)
도시락만들때 걸리는 최대시간을 123456789123LL으로 잡고
최소시간을 1으로 잡아준 다음
이분탐색해주면 된다...
도시락개수는 그냥 mid / arr[i]

I. 사탕 가져오기

그냥 DFS돌렸습니다
-1 케이스만 잘 구분해주세요

J. 숫자 회전

for(int i=0; i<n; i++){ printf("%c", s[(n*1000 + i - r) % n]); }

한줄컷!
r은 회전수고
%n을 통해서 범위밖에 안넘어가게 해준다음
음수인덱스 안되게
%n했을때 0이되는 큰수 n*1000을 더해줌

K. LED 파도타기

아까 E번이랑 비슷한 문제
나누는 / 나눈 나머지를 구하는 수 K가 10이 아니라 입력받는 수 N+1이라는것만
이해하면 쉽다.

void f(int t, int n){
  if(t==0) return;
  f(t/n,n);
  printf("%c", t%n==0?'0':'A'+ t%n -1 );
  return;
}

L. 동전 나열하기

DP 구현문제
dp[i][j] => j번째 동전을 뒤집었을때 i는 0,1 => 0은 앞, 1은 뒤일때의 경우의수

dp[0][i] = dp[0][i-1] + dp[1][i-1]; dp[1][i] = dp[0][i-1];

M. 보석 집게

하아니 이걸 왜 못풀죠(2)
일단 최댓값 / 최솟값 세그트리를 통해 한 구간 s,e 에서의 (최대-최소) 크기를 구함
이 크기를 구하는데 logN,
투 포인터 알고리즘 박으면 2N
시간복잡도는 O(NlogN) 되시겠다.

while(s<=e && e<=n){
  int mindata = querymin(1,1,n,s,e);
  int maxdata = querymax(1,1,n,s,e);
  //printf("{%d %d %d}\n", s,e, maxdata-mindata);
  if(maxdata-mindata <= k){
    maxv = max(maxv, (e-s+1));
    e++;
  }
  else s++;
}

N. 세종이의 보물찾기

S->T로 bfs후 거리저장,
T->G로 bfs후 거리저장
두개 더해주면 답이다.

O. 세종이의 보물찾기2

일단 입력이 참 깔끔하게도 이진트리형식으로 주어지기때문에
그대로 배열에 박아도 트리가 됨.
배열에 넣어주고 bfs한번 돌려주면 된다.

시대회인데 만점자가 11명쯤 나오는거 보면
어지간히 쉬운 셋이었음
"사전지식"을 요구하는 M번 문제 빼고는
그냥 다 무난무난하니 풀만했다.

OI순위탭을 세과영이 다먹었다던데
제발 시대회 상장 하나만 남겨주세요.....