글 읽기 - java 반례를 알고 싶습니다.

tiredpiru 1년 전 0

DP를 이용해서 풀었고, mem은 기존의 것을 저장하는 변수로 하였고, 3개의 가능성중에 가장 길이가 작은 것을 채택하는 방식으로 풀었습니다. 코드는 다음과 같습니다

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder[] mem;
    static int N;
    public static void main(String[] Args) throws IOException {
        N = Integer.parseInt(br.readLine());
        mem = new StringBuilder[N+1];
        DP(N);
        //개수 세기
        final StringBuilder sb = mem[N];
        int cnt = 0;
        for (int i = 0; i < sb.length(); i++) {
            if(sb.charAt(i) == ' ') {
                cnt++;
            }
        }
        System.out.println(cnt-1);
        System.out.println(sb);
    }

    static StringBuilder DP(int x) {
        if(x == 1) {
            mem[x] = new StringBuilder("1 ");
            return new StringBuilder("1 ");
        }

        ArrayList<StringBuilder> stringBuilderList = new ArrayList<>();

        if(x%3 == 0) {
            stringBuilderList.add(getBuilder(x,3));
        }
        if(x%2 == 0) {
            stringBuilderList.add(getBuilder(x, 2));
        }
        if(mem[x-1] != null) {
            stringBuilderList.add(new StringBuilder().append(x).append(" ").append(mem[x-1]));
        } else {
            stringBuilderList.add(new StringBuilder().append(x).append(" ").append(DP(x-1)));
        }

        int minIndex = 0;
        for (int i = 0; i < stringBuilderList.size(); i++) {
            if(stringBuilderList.get(minIndex).length() > stringBuilderList.get(i).length()) {
                minIndex = i;
            }
        }

        mem[x] = stringBuilderList.get(minIndex);
        return stringBuilderList.get(minIndex);
    }

    static StringBuilder getBuilder(int tar, int d) {
        if(mem[tar/d] != null) {
            return new StringBuilder().append(tar).append(" ").append(mem[tar/d]);
        }
        StringBuilder append = new StringBuilder().append(tar).append(" ").append(DP(tar / d));
        return append;
    }
}

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

문제

문제

출처

ICPC

java 반례를 알고 싶습니다.

tiredpiru 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말