★★ [백준][Java] 2304번 창고 다각형 (시뮬레이션)

 

솔직히 진짜 ㅈㄴ어려웠음.. 이게 실버2인게 말도 안됨 이거 뭔가 문제 자체를 이해하는 것은 어려운 것이 아닌데

이상하게 명쾌한 풀이법이 도저히 굴려봐도 안나왔음

일단 태그부터 정리하자면 자료구조, 스택인데 이거는 쓸 필요도 없고 스택 쓰면 for문 2배로 돌려야함

그렇다고 구현이라기엔 뭔가.. 구현하는 것은 아닌 것 같고

청소년들 보라고 만들어 놓은 수학 퍼즐 알고리즘 버젼으로 갖다 놓은 것 같음..

태그 - 시뮬레이션

 

첫번째 틀렸습니다 

아예 풀이 자체를 제대로 못했음 일단 풀이법 봤는데도

왼쪽에서 top으로 오른쪽에서 top으로라는 것이 도대체 무슨 의미인가 했더니

세모꼴의 산모양의 case의 공식을 적용해주면 

문제에서 주어지는 창고 다각형의 어떠한 case라도 전부 포괄하여 다각형의 면적을 구할 수 있다는 점이다..

이건 문제 자체의 풀이법에 관한 틀렸습니다임..

전형적인 풀이법 하나 그 종이 한장 차이에 갈리는 그런 문제임

풀이법을 알면 엄청 쉽고 모르면 그 풀이법때문에 시간이 엄청 걸리는 문제

 

참고 : https://codeung.tistory.com/253

 

 

 

두번째 틀렸습니다 

이건.. Line:33~34와 Line:49의 res값 초기화(?) 때문인데

나는 maxHeight기둥들이 만드는 면적은 가장 맨 처음에 넣어주는 것으로 res값을 초기화하려고 했음

 

maxHeight를 가지는 기둥(이하 TopPillar)들이 n개(1<=n<=1000)가 있다고 가정할 때

첫번째 TopPillar의 x좌표와

마지막번째 TopPillar의 x좌표를 이용해서

미리 TopPillar들(1개도 포함)이 만드는 다각형의 면적을 미리 구해놓는다는 것이 중요하다

이것을 실수로 

res += (lastIdx-firstIdx+1)*maxHeight; (x) 오답임 이걸로 썼음

res += (lastX-firstX+1)*maxHeight; (o)

위에 식으로 써서 틀렸음

 

솔직히 이거 실전에서 보면 얼타다가 못풀 것 같음 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
 
 
 
public class Main {
        
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException{
        int N = stoi(br.readLine());
        List<int[]> list = new ArrayList<>();
        int res = 0;
        
        int maxHeight = 0;
        for(int i=0; i<N; i++) {
            String[] str = br.readLine().split(" ");
            list.add(new int[] {stoi(str[0]), stoi(str[1])});
            maxHeight = Math.max(maxHeight, stoi(str[1]));
        }
        
        Collections.sort(list, (a,b)-> a[0]-b[0]);
        
        int firstIdx = -1;
        int lastIdx = -1;
        int firstX = -1;
        int lastX = -1;
        
        for (int i=0; i<list.size(); i++) {
            int[] curr = list.get(i);
            if(maxHeight==curr[1]) {
                if(firstIdx==-1) {
                    firstIdx = i;
                    firstX = curr[0];
                }
                lastIdx = i;
                lastX = curr[0];
            }
        }
        
        // 가장 높은 탑들을 미리 계산해주는거임
        res += (lastX-firstX+1)*maxHeight;
        
        // 왼쪽에서 maxHeight를 가진 탑으로
        int[] preStick = new int[] {0,0};
        
        for(int i=0; i<=firstIdx; i++) {
            int[] currStick = list.get(i);
            if(preStick[1]<currStick[1]) {
                res+= preStick[1]*(currStick[0]-preStick[0]);
                preStick = currStick;
//                System.out.println(currStick[0]+" "+currStick[1]);
            }
            
        }
//        System.out.println();
        
        
        // 오른쪽에서 maxHeight를 가진 탑으로
        preStick = new int[] {0,0};
        for(int i=list.size()-1; i>=lastIdx; i--) {
            int[] currStick = list.get(i);
            if(preStick[1]<currStick[1]) {
                res+= preStick[1]*(preStick[0]-currStick[0]);
                preStick = currStick;
//                System.out.println(currStick[0]+" "+currStick[1]);
            }
        }
        
        System.out.println(res);
        
//        bw.write("");
//        bw.flush();
//        bw.close();
    }
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}