개발자 톡

연습문제 톡 징검다리

질문에 있는 모든 반례를 다 넣었는데 잘 나오거든요.. 틀린 이유를 진짜 못찾겠어요 반례좀 부탁드려요.

등록일
2024-07-10 22:25:21
조회수
45
작성자
lizzey2
import java.io.*;
import java.util.*;

public class Main {
    static int N;
    static int arr[];
    static int count[][]; //각 인덱스에 돌 개수 최댓값을 넣어줌 (count[각 돌의 인덱스][넘어가는 순서에, 더 작은 돌이 생기게 되면, 카운트를 다시 세기]
    static int answer[]; //각 돌을 시작으로 뛰었을 때의 돌 개수 최댓값
    static int answerMax = 1; //최종 정답

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        arr = new int[N];
        count = new int[N][N];
        answer = new int[N];
        for (int n = 0; n < N; n++) {
            //count 배열은 1으로 초기화
            for (int m = 0; m < N; m++)
                count[n][m] = 1;
            arr[n] = Integer.parseInt(st.nextToken());
            answer[n] = 1;
        }

        int start = 0; //첫번째 인덱스부터 마지막 인덱스까지 돌의 최대개수 N개 구하기
        int i = 0; //처음에는 start와 같은 인덱스였다가, 자기보다 더 큰 값을 만나면, 그 지점부터 더 큰걸 찾기 위해 i는 변함
        int countIndex = 0;
        while (start < N) {
            //i가 N번째거나, start가 N번째이면 while문 벗어나기
            if (i >= N) break;
            for (int j = (i + 1); j < N; j++) { //i+1부터 i와 비교해서 더 큰값인지 확인
                if (arr[j] > arr[i]) {
                    //더 큰 돌이면, count 증가 그리고 i는 j부터 다시 시작
                    count[start][countIndex]++;
                    i = j;
                    continue;
                }
                if (arr[i] > arr[j] && arr[start] < arr[j]) { //start지점보다는 크지만, 현재지점(i)보다 미래지점(j)가 더 작으면, 다시 카운트를 해봐야 함
                    countIndex++;
                    count[start][countIndex]++;
                    i = j;
                }
            }
            start++; //N까지 다 돌고나면, start 지점을 하나 뒤로 옮겨서 count를 다시 구하기
            i = start;
        }

        for (int k = 0; k < N; k++) {
            int maxCount = 1;
            for (int m = 0; m < N; m++) {
                if (count[k][m] > maxCount) maxCount = count[k][m];
            }
            answer[k] = maxCount;
            if (answer[k] > answerMax) answerMax = answer[k]; //answerMax에 각 시작한 돌의 인덱스에서의 최대 돌 개수 중 최댓값 넣기
        }
        System.out.println(answerMax);
    }
}


#징검다리

이 카테고리의 톡 더보기