KOI 2016 초등부 해설

1. 방 배정

int arr[2][6]

arr[i][j]: 성별이 i이고 학년이 j인 사람 수 count 하고

$$\sum(arr[i][j]+K-1)/K)$$  

로 구하면 된다.

 

2. 타일 장식물

슬라이딩 윈도우 기법으로 배열 크기 2로만 풀 수 있다.

arr[i]: 직사각형의 한 변 길이

arr[(i+1)%2]: 직사각형의 다른 변 길이

arr[(i+1)%2 = arr[i%2]+arr[(i+1)%2]

 

3. 리조트

dp 문제이다.

dp[i][j]: i일째까지 리조트 이용하고 j개의 쿠폰이 남았을 때 앞으로 필요한 최소 비용

i일째까지 해결되었으니 j=i+1일 째부터 확인하는데 만약 가지 못하는 날이 있으면 j를 쭉 skip한다.

그리고 처음으로 가야하는 날이 있으면 그 때부터

1. 5일권 : 37000+dp[j+4][num+2]

2. 3일권 : 25000+dp[j+2][num+1]

3. 1일권 : 10000+dp[j][num]

4. 쿠폰 이용: dp[j][num-3]

이 때 dp[i][j]=min(1~4)

4. 장애물 경기

여러번 틀렸다. 초등부 문제도 바로 못 푸니 더 열심히 해야겠다.

가장 먼저 푼 풀이는 장애물을 x좌표 오름차순으로 정렬시키고 백트래킹으로 시도했다. 구현은 성공했지만 당연히 시간초과가 났다.

결국 공식 해설을 보고 아이디어를 얻었다. 

각 점이 어떻게 분기되는지 위의 그림을 보자. 

typedef pair<int,int> P

set<P> s를 선언하고(각 점을 set에 insert할 것이다)

s.insert(P(43,0));으로 시작한다.

s에 저장되는 P의 첫번째 원소는 각 분기점의 y좌표를 의미하고 두번째 원소는 그 y좌표에 도달할 때까지의 상하 이동 거리를 의미한다.

다음 장애물이 [yl,yh]라 하면

s에 저장되어 있는 분기점 중 yl초과 yh미만(이상, 이하로 해도 되는데 그 이유는 어차피 장애물 끝에 걸려도 바뀌지 않기 때문이다.)을 찾고(lower_bound함수 이용)

그 점들(erase해줘야 됨)이 분기되어 yl과 yh로 나뉘어지는데

그 때 yl로 분기되는 점들 중 가장 이동거리가 짧은 것과 yh로 분기되는 점들 중 가장 이동거리가 짧은 것을 set에 추가하면 된다. 따라서 yl과 yh사이의 점들에 대해 vector<P>에 (yl or yh,이동거리)를 쭉 저장해놓고 (탐색 과정 중의 set원소는 다 삭제) 마지막에 정렬시켜서 이동거리가 최소인 점들을 다시 insert시키면 된다.

 

구현의 방식은 아래의 코드를 참고하자

        set<P>::iterator it;
        it=s.lower_bound(P(yl,0));
        vector<P> m1,m2;
        while(it!=s.end()){
            int y=(*it).first;
            if(y>=yh) break;
            long long len=(*it).second;
            m1.push_back(P(yl,len+y-(long long)yl));
            m2.push_back(P(yh,len+yh-(long long)y));
            set<P>::iterator tmp=it;
            it++;
            s.erase(tmp);
        }
        if(!m1.empty()){
            sort(m1.begin(),m1.end());
            sort(m2.begin(),m2.end());
            s.insert(m1.front());
            s.insert(m2.front());
        }

각 장애물에 대해 insert하는 과정은 O(X) 이다. 이 때 X는 분기점의 개수

하지만 분기점의 크기가 얼마나 커질 수 있을 까? 개수 2배씩 증가한다고 해도 logN개이다.

장애물의 개수는 N이므로 O(NlogN)의 시간복잡도가 걸린다.