글 읽기 - 92%에서 자꾸 틀렸다고 뜨는데 반례를 못찾겠습니다.

skawls5028 6년 전 0

1자리숫자의경우 K=0 일때

2자리 숫자의경우 뒷자리가 0일때 K>1이면 -1처리를 했습니다.

import java.util.ArrayList;
import java.util.Scanner;

/**
 * Created by NamjinCho on 2017-10-07.
 */
public class Trade {

    static char arr[];
    static int ans;
    static int wc;
    static int leng;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            String line[] = sc.nextLine().split(" ");

            line[0] = line[0].trim();
            line[1] = line[1].trim();
            wc = Integer.parseInt(line[1]);
            arr = new char[line[0].length()];
            for (int i = 0; i < line[0].length(); i++) {
                arr[i] = line[0].charAt(i);
            }
            leng = arr.length;

            int count = 0;
            int insertIdx = 0;

            ans=0;
            if(leng==1)
                ans=-1;
            else if(leng==2)
            {
                if(arr[1]==0 && wc>1)
                    ans=-1;
            }
            if(ans==0) {
                dfs(0, 0);
            }

            System.out.println(ans);

    }

    public static ArrayList<Integer> findMaxIdx(int start) {
        int maxIdx = start;
        for (int i = start + 1; i < arr.length; i++) {
            if (arr[maxIdx] < arr[i]) {
                maxIdx = i;
            }
        }
        ArrayList<Integer> result = new ArrayList<>();
        for(int i=start;i<arr.length;i++)
            if(arr[i] == arr[maxIdx])
                result.add(i);
        return result;
    }

    public static void dfs(int start,int count)
    {
        if(count<wc && start < arr.length){
            ArrayList<Integer> maxs = findMaxIdx(start);

            for(int i=0;i<maxs.size();i++)
            {
                if(maxs.get(i)==start)
                {
                    dfs(start+1,count);
                    continue;
                }
                swap(start,maxs.get(i));
                dfs(start+1,count+1);
                swap(start,maxs.get(i));
            }
        }

        //System.out.println(getString() +" "+ count +" "+start);
        if (count < wc) {
            if ((wc - count) % 2 == 1) {
                swap(arr.length - 1, arr.length - 2);
                String r = getString();
                ans = Math.max(ans,Integer.parseInt(r));
                swap(arr.length-1,arr.length-2);
            }else
            {
                String r = getString();
                ans = Math.max(ans,Integer.parseInt(r));
            }
        }else
        {
            String r = getString();
            ans = Math.max(ans,Integer.parseInt(r));
        }
    }
    public static void swap(int s, int e) {
        char tmp = arr[s];
        arr[s] = arr[e];
        arr[e] = tmp;
    }
    public static String getString()
    {
        String r="";
        for(int i=0;i<arr.length;i++)
            r=r+arr[i];
        return r;
    }
}

mc_progw12 3년 전 2

이 글은 3년 전 글이지만 훗날 이 문제를 푸실 분들을 위해 글을 남깁니다.

정답 코드에서 -1 처리 부분을 빼면 92%에서 에러가 나는 것을 보아 -1 문제가 분명합니다.

질문자님 말은 맞는데, 3자리일 때 뒤 두 자리가 모두 0이여도 답은 -1이 됩니다.

그래서 방법은, 교환을 한 번이라도 할 수 없으면 -1을 출력하게 하면 됩니다.

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

문제

문제

출처

ICPC

92%에서 자꾸 틀렸다고 뜨는데 반례를 못찾겠습니다.

skawls5028 6년 전 0

mc_progw12 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말