제 1회 세종정보올림피아드

제 1회 세종정보올림피아드 후기

제 1회  즐겁게 고등부 1등 먹고 왔습니다.

친구들과 택시 타고 세종 SW 교육센터에 도착.

12시~12시 30분 사이 입실이라 근처에 있는 칼국수 집에서 든든하게 한 그릇 뚝딱.

 

오후 1시부터 5시까지 4시간 동안 진행했습니다.

 

풀이 스케치

A: 스위핑 문제.

일단 기지국이 원점이 되도록 좌표들을 평행이동한다.

레이저가 일직선 형태로 나아가므로 점들을 x>0 인 것과 x<0일 때로 나눈다.

각도 순으로 정렬 후 스위핑 해서 같은 각도에 있는 점들의 최대 개수를 구한다.

 

B: 이차원 dp

꽤 신선하게 다가왔던 문자열 + dp 문제

문자열 s가 주어진다.

이차원 격자판에 알파벳들이 나열되어 있고,  격자판 위 점에서 상하좌우로 움직일 수 있다. 가능한 모든 경로(갔던 점 또 갈 수 있음!! <- 매우 중요)에 대해 경로들의 알파벳을 모두 이었을 때 s와 같아지는 경우의 수를 구하기. 단, 경로 중에서 첫 점과 끝 점을 제외하고 중간에서 한 점을 지울 수 있다.

 

Dp[flag][i][j][k]를 ‘flag번 지웠을 때 i,j번 칸까지 s[k]까지 만들 수 있는 경우의 수’로 정의하자.

이때 dfs로 다이나믹 백트래킹하면서 풀면  구현이 간편하다.

 

C: 이진트리 순회 + 세그먼트 트리

노드의 왼쪽 / 오른쪽 개념을 정의한다.

이를 이용해 특정 구간의 구간합을 구하는 문제.

 

소수의 개수를 구하라고 했지만 노드의 값이 1~10000 사이 정수이므로 전처리 해놓고 소수인지 여부를 1/0으로 정의하면 구간합 문제가 된다.

주어진 이진트리를 ‘중위 순회’ 하여 넘버링을 다시 해주면 노드들을 가장 왼쪽에서 오른쪽으로 정렬할 수 있다. 이제 연속된 구간의 합을 구하고,  특정 노드의 값을 업데이트하는 문제로 바뀐다.
이는 구간합 세그먼트 트리를 사용하여 해결할 수 있다.

 

D:  비트마스킹 dp

1*1, 1*2 블럭으로 N*M 타일 채우기 문제를 확장한 문제

N*M 칸 중에서 특정 칸들만 검은 색일 때 검은색 칸을 블럭들로 전부 채우는 방법의 수를 mod로 나눈 나머지를  구하는 것.

N,M이 10 이하로 작으므로 비트마스킹으로 각 행의 정보를 저장할 수 있다.

서브태스크 1이 N=1일 때, 즉 1차원일 때이다. 이 경우 연속한 칸들의 개수를 세주어 그 개수번째 피보나치 수들의 곱으로 정답을 나타낼 수 있다.

Ex) 1 1 1 0 0 1 1로 행 정보가 주어진다면

총 경우의 수는  1*3 타일을 채우는 경우의 수 X  1*3 타일을 채우는 경우의 수가 된다.

이를 이용해 총 문제를 풀 수 있다.

검은색 칸들을 1. 지금 내가 채울 칸(1*1 또는 1*2 블럭으로 채움) 또는 2. 뒷 행으로 처리를 미룰 칸(2*1블럭으로 채움)에 따라 1/0으로 비트마스킹 한다.

Dp[i][st]: i번째 행을 st의 상태로 채울 때 가능한 경우의 수

Dp[i][st] = sum(dp[i][pre_st] * val[modified_st]

이제 다음 행에서는 그 전 행에 검은색이나 아직 채워지지 않은 칸이 있다면 현재 상태에 바로 채워버리고 남은 칸들에 대해 섭태 1에서 구한 (피보나치 수들의 곱) 을 구해 전행의 dp값에 곱해 현재 행의 dp 테이블을 채울 수 있다.

물론 적절한 전처리로 피보나치 수의 곱과 각 행에 대해 가능한 상태를 미리 구해놓을 수 있다.

여담으로 min(N,M)이 10이하라면 max(N,M)이 1000 이상으로 커져도 빠른 시간 내에 문제를 해결할 수 있다. Dp 토글링으로 가능하다.

 

2:49 후 퇴실

장첸처럼 머리를 묶으신 잘생기 남자 선생님께서 고등부 고사장의 운영을 맡으셨는데 친절하시고 문제에 모호한 부분이 있으면 명확하게 대답해주셔서 좋았다.

 

서브태스크 분배가 정말 좋았다.

4번 문제에서 1번 섭태를 빨리 구현한 건 신의 한 수 !