[codetree] 프로그래밍 연습 _시뮬레이션1_ 구간 칠하기 C++

안녕하세요. 우당탕탕 개발일지 입니다. 꾸준히 문제 풀기 다시 시작해보겠습니다. 

codetree가 마음에 들어 순서대로 풀 것 같습니다. 아자아자 화이팅!

 

 

 

 

1. 최대로 겹치는 구간

 

1. 가장 많이 겹치는 구간 구하기 -> sort 함수

2. -100~+100구간에 음수 포함 -> 입력 +100 해서 저장.

3. 구간 -> 시작,끝 구간을 각각 배열 2개에 저장

4. 구간에 몇번 들어가는지 카운트 -> 시작~끝까지 count

 

#include <iostream>
#include<algorithm>
using namespace std;

int main() {
    

    int n;
    cin>>n;

    int a[200];
    int b[200];

    for(int i=0; i<n; i++)
    {
        cin>>a[i]>>b[i];
        a[i]+=100;
        b[i]+=100;

       
        
    }


    int k[200];
    for(int i=0; i<200; i++)
    {
        k[i]=0;
    }

    
    int x=0;

    while(true)
    {
        if(x>n)
            break;

        for(int i=a[x]; i<b[x]; i++)
        {
            k[i]++;

            //cout<<i<<" "<<a[x]<<" "<<b[x]<<" "<<k[i]<<"\n";
           
        }
        x++;
   
    
    }
  
    sort(k,k+200);

    cout<<k[199];

    


    return 0;
}

 

 

 

2. 왔다 갔던 구역2  

#include <iostream>
using namespace std;

int main() {

    int n; 
    cin>>n; 

    int a[1000];
    int b[1000];

    int cur=0;

    int arr[2000]={0};

    for(int i=0; i<n; i++)
    {
        int x;
        char c;

        cin>>x>>c;
        
        

        if(c=='R')
        {
           a[i]=cur;
           b[i]=cur+x;

           cur=cur+x;
            
            
        }
        else if(c=='L')
        {  
            a[i]=cur-x;
            b[i]=cur;

           cur=cur-x;

           
        } 

            a[i]=a[i]+1000;
            b[i]=b[i]+1000;


    }




    for(int i=0; i<n; i++)
    {   
       
        for(int j=a[i]; j<b[i]; j++)
        {
            arr[j]++;

        }
        

    }


    int count=0; 
    for(int i=0; i<2000; i++)
    {
        if(arr[i]>=2)
        {
            count++;

           
        }
    }
    
    cout<< count; 
    
    // Please write your code here.
    return 0;
}

 

 

3. 흰검 칠하기

-> 원래는 define 안쓰고 배열에 바로 숫자 썼는데 컴파일 시간이 너무 오래 걸려서 define 사용함.

(#define은 메모리를 사용하지 않음)

#include <iostream>
using namespace std;

#define MAX_K 100000

int main() {
    // Please write your code here.


    int n;
    cin>>n; 

    int x;
    char c;


    // 4개 이상되는거 걸러내기 위해서 필요함. 
    int cnt_b[2*MAX_K+1];
    int cnt_w[2*MAX_K+1];

    //색 넣을 배열
    int arr[2*MAX_K+1];
   
    int cur=MAX_K;

    for(int i=0; i<n; i++)
    {
        cin>>x>>c;

        if(c=='R')
        {
           while(true){

            --x;
            arr[cur]=2;
            cnt_b[cur]++;
            
            if(x!=0) cur++;
            else break;
           

           }   

        }
        else
        {
            while(true)
            {   
                --x;
                arr[cur]=1;
                cnt_w[cur]++;
                
                if(x!=0) cur--;
                else break;

            }            


        }


      
    }


    int w=0,b=0,g=0;
    for(int i=0; i<2*MAX_K; i++)
    {
        if((cnt_b[i]>=2) && (cnt_w[i]>=2))
        {
            g++;
        }
        else if(arr[i]==1)
        {
            w++;
        }
        else if(arr[i]==2)
        {
            b++;
        }
    }

    cout<<w<<" "<<b<<" "<<g;
    return 0;
}