글 읽기 - 같은 수 만들기 반례가 필요합니다.

seung0916 2년 전 0

수는 증가구간(같은수포함 감소만아니면 증가구간)과 감소구간을 갖는다.

증가구간의 시작점과 끝점이 있다고 했을때, 증가구간의 시작점과 증가구간의 끝의 차이를 메꾸어주면 모두 같은수로 만들어진다.

감소구간은 감소의 끝점이 증가구간의 시작점이된다.

증가구간으로 시작할 경우는, 미리 저장해둔 arr[0]이 min이된다.

감소구간으로 시작할 경우는 미리 저장해둔 arr[0]이 max가된다.

모두 평평한 구간으로 만들다보면 항상 내림차순의 계단구조가된다. ( * 첫 시작이 감소구간일경우 첫 감소구간만 계단 대신 감소구간)

모든 수를 탐색하였을 때 증가구간으로 끝난다면, 해당 구간을 채우고, 가장 높은구간과 현재 자신의 고점을 비교하여 자신이 고점이면

정답, 차이가 있다면 그 차이만큼을 계산해준다.

감소구간으로 끝난다면, 현재의 마지막 요소가 가장 작은 수이기때문에, 최고점과의 차이를 정답에 더해준다.

이 논리로 정답코드랑 같이 예시를 돌려봐도 대부분 동일한 결과가 나오는데 오답처리를 받아서 궁금합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
/*
    수는 증가구간(같은수포함 감소만아니면 증가구간)과 감소구간을 갖는다.
    증가구간의 시작점과 끝점이 있다고 했을때, 증가구간의 시작점과 증가구간의 끝의 차이를 매꾸어주면 모두 같은수로 만들어진다.
    감소구간은 감소의 끝점이 증가구간의 시작점이된다.
    증가구간으로 시작할 경우는, 미리 저장해둔 arr[0]이 min이된다.
    감소구간으로 시작할 경우는 미리 저장해둔 arr[0]이 max가된다.
    모두 평평한 구간으로 만들다보면 항상 내림차순의 계단구조가된다.  ( * 첫 시작이 감소구간일경우 첫 감소구간만 계단 대신 감소구간)
    모든 수를 탐색하였을 때 증가구간으로 끝난다면, 해당 구간을 채우고, 가장 높은구간과 현재 자신의 고점을 비교하여 자신이 고점이면
    정답, 차이가 있다면 그 차이만큼을 계산해준다.
    감소구간으로 끝난다면, 현재의 마지막 요소가 가장 작은 수이기때문에, 최고점과의 차이를 정답에 더해준다.
 */
public class BOJ2374 {

    public static void main(String[] args) throws Exception{
        int min, max=0, answer=0, N, arr[],highest=0, code=1;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if(highest<arr[i])
                highest = arr[i];
        }
        max = arr[0];
        min = arr[0];
        int i=0;
        while (i< N-1) {
            while (i<N-1&&arr[i]<=arr[i+1]){
                i++;
                code =1;
            }
            max = arr[i];
            answer +=(max - min);
        
            while (i<N-1&&arr[i]>=arr[i+1]){
                i++;
                code =0;
            }
            min = arr[i];
        }

        if (code ==1){  //고점 종료
            answer += (highest>max)? (highest-max) : 0;
            System.out.println(answer);
        }else{  //저점종료시 마지막 저점 .
            System.out.println((answer+highest-min));
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.