글 읽기 - 반례를 찾지 못하고 있습니다 ㅠ..

polakr 5년 전 0

처음에 생각을 못해서 힌트를 얻어서 증가하는 수열중 가장 긴건 그대로 두고 그 외의것을 움직이면 최소의 수로 정렬할 수 있다고 해서 LIS로 찾아서 (전체길리-최대 증가 부분순열 길이)를 구하는 방식으로 접근했습니다. 그렇지만 틀렸다는데 제가 생각할 수 있는 경우를 몇개 넣어봐도 잘 동작을 해서 무엇이 문제인지 모르겠습니다 ㅠㅠ..

---자문자답

bw.write(ans + '\n');

이 부분을

bw.write(Integer.toString(ans) + '\n');

이렇게 수정하니 정답이 되었습니다 ㅎㅎ

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }

        // '전체길이' - '가장 긴 증가하는 부분순열의 길이'로 최소한 움직여야하는 원소의 개수를 구합니다.
        int ans = N - LIS(nums);
        bw.write( ans + '\n');
        bw.flush();

        return;
    }

    public static int LIS(int[] nums) {

        // d배열에 각 원소를 기준으로하는 증가하는 순열의 길이를 저장합니다.
        int[] d = new int[nums.length];
        Arrays.fill(d, 1);
        for (int i = 1; i < nums.length; i++) {
            int max = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && d[j] > max) {
                    max = d[j];
                }
            }
            d[i] = max + 1;
        }
        
        // 가장 긴 증가하는 부분수열의 길이를 찾습니다.
        int max = 0;
        for (int i = 0; i < d.length; i++) {
            if (max < d[i]) {
                max = d[i];
            }
        }

        return max;
    }
}

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

문제

문제

출처

ICPC

반례를 찾지 못하고 있습니다 ㅠ..

polakr 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말