[SWEA] 9232 한길이의 생일 선물

 

이 문제는 투 포인터의 개념으로 풀 수 있다!

디스크가 쌓여져있는 모습을 생각하며 전처리를 해줘야한다

각 디스크 자리에 들어갈 수 있는 최대의 수를 미리 구해보자!

 

그리고 아래서부터 들어가 쌓이므로 거꾸로 최대의수 배열을 보며 디스크를 넣어보면 된다

 

while문을 통해 내가 현재 넣을 수 있는 가장 아래칸을 찾고

위치를 계속 갱신해 나간다

그리고 마지막으로 우린 뒤집어서 봤으므로 다시 위치를 뒤집는다!

 

디스크를 넣을 수 있는 N개의 칸을 모두 다 지나쳐 버리면 답은 0이 된다!

 

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 
int arr[300030];
int disc[300030];
int minn[300030];
 
int main(){
    //freopen("input.txt","r",stdin);
    int tc; scanf(" %d",&tc); int c=1;
    while(tc--){
        memset(arr,0,sizeof(arr));
        memset(disc,0,sizeof(disc));
        memset(minn,0,sizeof(minn));
 
        int n,q; scanf(" %d %d",&n,&q);
        
        for(int i=0;i<n;i++) scanf(" %d",&arr[i]);
        for(int i=0;i<q;i++) scanf(" %d",&disc[i]);
        int temp=1e9;
        for(int i=0;i<n;i++){
            temp = min(temp,arr[i]);
            minn[i]=temp;
        }
        reverse(minn,minn+n);
        
        int pos=0;
        int ans=0;
        bool check= true;
        for(int i=0;i<q;i++){
            while(pos < n && (minn[pos] < disc[i])) pos++;
            if(pos==n) {
                check=false; break;
            }
            ans = ++pos;
        }
        ans = (check) ? n-ans+1 : 0;
        printf("#%d %d\n",c++,ans);
    }
}