화살표 그리기 [BOJ 15970]

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
• 주어진 자료는 무엇인가?
• 조건은 무엇인가?
• 우리가 문제를 풀기 위해 주어진 자료가 충분한가?
• 숨겨진 조건이나 자료가 있는가? 그렇다면 그 것을 다른 방법으로 해석해보라. 

- 문제가 무엇인가?

-> 점의 좌표와 색깔을 나타내는 

-> 이것을 어떻게 나타내는가?

-> 문제가 무엇인가?

-> 어떻게 코드를 수정할 것인가?

-> 점을 pair로 관리하면 어떠한가?

-> 즉, 값과 타입을 pair로 관리하면 어떠한가?

-> 그러한 경우 무엇으로 정렬해야 하는가?

-> value로 정렬을 해야 한다

-> 어떻게 정렬을 하는가?

-> 

 

- 문제가 무엇인가?

-> 어떻게 계산을 할 것인가?

-> 계산을 한다는 것이 무엇인가?

-> 어떤 계산을 해야 하는가?

-> 점의 색깔이 동일한지부터 확인해야 한다

-> 지금과 다음의 점의 색깔이 동일해야만, 계산을 해야 한다

-> 그 다음에 무엇을 하는가?

-> 해당 점에서 아래, 위로 계산이 가능한지 판단해야 한다

-> 만약에 아래, 위로 가능하다면, 둘 다 계산을 한다

-> 그것이 아니라면 한 쪽으로만 계산을 한다

-> 이것을 어떻게 구현하는가?

-> 

 

- 문제가 무엇인가?

-> 어떻게 계산하는가?

-> 계산을 한다는 것이 무엇인가?

-> 어떤 케이스가 존재하는가?

-> 케이스에 대한 이해가 핵심

 

 

0 1     1 2

3 1     4 2 

5 1   

- 앞 뒤의 점 중에서 가까운 점을 선택하면 되지 않는가?

-> 어떻게 그렇게 선택하는가?

-> 3 2 2 3 3 

 

0 1   7 2

3 1  10 2

4 1

6 1

9 1

 

3  3 

1  3

1

2

3

 

- 문제가 무엇인가?

-> 만약 점이 2개라면 어떠한가?

-> 점이 2개라는 것이 무엇인가?

-

 

2. 계획

• 전에 비슷한 문제를 알고 있는가?
• 이 문제를 푸는데 있어서 유용하게 쓸 수 있는 지식은 무엇인가?
• 비슷한 문제를 풀어본 적이 있다면 그 것을 활용할 수 있는가?
• 만약 문제를 풀 수 없다면 문제를 더 단순하게 하기 위해서 주어진 조건을 버려보아라
• 주어진 자료로부터 유용한 것을 이끌어 낼 수 있는가?
• 자료는 모두 사용했는가?
• 조건을 모두 사용했는가?
• 문제에 포함된 핵심적인 개념은 모두 고려했는가?

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

import java.util.*; 


class Pair implements Comparable<Pair>{
    
    int x;
    int y;
    
    public Pair(int x, int y){
        this.x = x;
        this.y = y; 
    }
    
    
    @Override
    public int compareTo(Pair p){
        if(this.y == p.y){
            return this.x - p.x;
        }
        return this.y-p.y; 
    }
    
}



public class Main {
    public static void main(String args[]) {
      
      Scanner sc = new Scanner(System.in);
      int answer = 0; 
      
      int N = sc.nextInt();
      ArrayList<Pair> arr = new ArrayList<>();
      
      
      for(int i=0; i<N; i++){
          int num = sc.nextInt();
          int type = sc.nextInt();
          
          arr.add(new Pair(num, type));
      }
      
      Collections.sort(arr);
      
      int len = arr.size();
      
      for(int i=0; i<len; i++){
          
         
         if(i == 0){
             answer += (arr.get(1).x-arr.get(0).x);
         }else if(i == len-1){
             answer += (arr.get(len-1).x-arr.get(len-2).x);
         }else{
             
             if( (arr.get(i-1).y == arr.get(i).y) && (arr.get(i).y == arr.get(i+1).y)){
                 answer += Math.min( (arr.get(i).x - arr.get(i-1).x), (arr.get(i+1).x - arr.get(i).x));
             }else if( (arr.get(i-1).y == arr.get(i).y) && (arr.get(i).y != arr.get(i+1).y) ){
                 answer += (arr.get(i).x-arr.get(i-1).x);
             }else{
                 answer += (arr.get(i+1).x-arr.get(i).x);
             }
             
             
         }
         
         
         
         
          
      }
      
      
      
      
      System.out.println(answer);
      
      
      
      
      
      
    }
}

[참고 풀이]

import java.util.*;

public class Main {
    
    
    public static int N;
    public static ArrayList<Integer>[] arr; 
    
    
    
    public int toLeft(int i, int pos){
        
        if(pos == 0){
            return Integer.MAX_VALUE;
        }else{
            return arr[i].get(pos)-arr[i].get(pos-1);
        }
        
        
    }
    
     
    public int toRight(int i, int pos){
        
        if(pos == arr[i].size()-1){
            return Integer.MAX_VALUE;
        }else{
            return arr[i].get(pos+1)-arr[i].get(pos);
        }
        
        
    }
    
    
    
    public static void main(String args[]) {
      Main T = new Main();
      Scanner sc = new Scanner(System.in);
      
      int answer = 0; 
      
      N = sc.nextInt();
      arr = new ArrayList[N+1];
      
      for(int i=1; i<=N; i++){
          arr[i] = new ArrayList<Integer>();
      }
      
      for(int i=1; i<=N; i++){
          int pos = sc.nextInt();
          int type = sc.nextInt();
          
          arr[type].add(pos);
      }
      
      
      for(int i=1; i<=N; i++){
          Collections.sort(arr[i]);
      }
      
      
      for(int i=1; i<=N; i++){
          
          int len = arr[i].size();
          
          for(int j=0; j<len; j++){
              
              int leftDist = T.toLeft(i,j);
              int rightDist = T.toRight(i,j);
              
              answer += Math.min(leftDist, rightDist);
          }
          
      }
      
      
      System.out.println(answer);
      
      
      
      
    }
}

4. 반성

• 문제를 다른 방식으로 해결할 수 있는가?
• 결과나 방법을 어떤 다른 문제에 활용할 수 있는가?
• 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?
• 어떻게 하면 더 효과적으로 문제를 해결할 수 있는가?

- 어떻게 하면 더 효율적으로 문제를 해결할 수 있는가?

-> 문제의 케이스를 잘 고려해야 한다. 

 

- toLeft, toRight 와 같은 메소드를 선언해서 사용할 수 있다

- ArrayList<Integer>[] arr과 같은 형식은 매우 자주 사용되므로, 반드시 익혀놓도록 하자

- 각각의 ArrayList를 Collections.sort 해서 사용할 수 있다.