ACM ICPC/2012스터디

스터디

8월 9일

내용

• 참가자 : 김태진, 정종록, 이민규, 이진규, 남성준, 권영기
• 진행 방식에 대한 회의
  • 우선 www.dovelet.com 더블릿 사용
• 오늘 푼 문제
  • 아시아 정보올림피아드/koi_aio: [1] (옥상 Vol1 koi_aio)
  • 초콜릿/coci_coko : [2] (옥상Vol3 coci_coko)
• 숙제로 풀 문제
  • 이기적인 소/usa_selfish : 이기적인 소

풀이

coci_coko/권영기
koi_aio/권영기

8월 14일

내용

• 참가자 : 김태진, 정종록, 권영기, 곽병학
• 진행 방식에 대한 회의
  • 풀어온 문제를 가지고 논해보고, 다음 문제를 정하는 방식.
  • Programming Challenge에서 알고리즘 당 두문제 정도 풀기.
  • www.dovelet.com 더블릿 옥상에서 한 문제 풀기.
  • Programminc Challenge 문제에 더욱 높은 우선순위를 둠. - [3]

• 금요일 까지 풀어올 문제.
  • Doublets - [4]
  • Where's Waldorf - [5]
  • koi_spra - [6] (dovelet)

풀이

import java.util.Arrays; 
import java.util.Comparator; 
import java.util.Scanner; 
  
class pair { 
    int a; 
    int b; 
      
    pair(int a, int b) { 
        this.a = a; 
        this.b = b; 
    } 
} 
  
public class Main{ 
    public static void main(String ar[]) {       
        Scanner scan = new Scanner(System.in); 
        int n = scan.nextInt(); 
          
        pair[] p = new pair[n]; 
          
        for(int i=0; i<n; i++) 
            p[i] = new pair(scan.nextInt()-1, scan.nextInt()-1); 
          
        Arrays.sort(p, new myCmp()); 
        int last = p[n-1].b; 
          
        int[] ans = new int[last+1]; 
          
        Arrays.fill(ans, 0, p[0].b, 0); 
          
        for(int i=0; i<n; i++) { 
            if(i != 0)  
                Arrays.fill(ans, p[i-1].b, p[i].b, ans[p[i-1].b]); 
                  
            ans[p[i].b] = Math.max(ans[p[i].a] +1, ans[p[i].b-1]);               
        } 
  
        System.out.println(ans[last]); 
        /*for(int i=0; i<last+1; i++) 
            System.out.println(ans[i] + " ");*/
                  
    } 
} 
  
class myCmp implements Comparator<pair> { 
  
    @Override
    public int compare(pair o1, pair o2) { 
        if(o1.b < o2.b) return -1; 
        else if(o1.b == o2.b) { 
            if(o1.a < o2.a) return -1; 
            else if(o1.a == o2.a) return 0; 
            else return 1; 
        } 
        else return 1; 
    } 
}