글 읽기 - 부가적인 문제가 있는지 확인해주실 수 있나요?

ohj8447 3년 전 1

해당 프로그램을 실행하면 1%부터 틀렸다고 나옵니다.

참조를 잘못했나해서 참고했던 C++ 코드를 테스트 실험해보니 해당 코드는 통과했고요

unitTest에서도 많은 예제를 적용해 보지는 않았으나 문제없이 통과합니다.

첨부한 코드에서 문제되는 부분이 있을까요?

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

public class Main {
public static void main (String[] args) {
        try {
            BufferedReader qr = new BufferedReader(new InputStreamReader(System.in));

            ParkSungWon psw = new ParkSungWon();

            int N = Integer.parseInt(qr.readLine());
            psw.initialize(N);
            for(int i = 0 ; i<N; i++) {
                    psw.addV(qr.readLine());
            }
            psw.setK(Integer.parseInt(qr.readLine()));
            psw.run();

            String rst = psw.getResult();
            System.out.println(rst);
        }catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

class ParkSungWon {
    private static final int LENGTH_MAX = 50;
    int n;
    int k;
    int ten[];
    int length[];
    ArrayList<String> v;

    int a[];
    int dp[][];

    public void initialize(int n) {
        this.n = n;

        v = new ArrayList<>();
        a = new int[n];
        length = new int[n];
        ten = new int[LENGTH_MAX+1];
    }

    public void addV(String v) {
        length[this.v.size()] = v.length();
        this.v.add(v);
    }

    public void setK(int k) {
        this.k = k;
        dp = new int[(1 << n)][k];

        int tmp = 10;
        for( int i = 1; i <= LENGTH_MAX; i++) {
            ten[i] = tmp % k;
            tmp = ten[i] * 10;
        }

        for (int i = 0 ; i < v.size(); i++) {
            String t = v.get(i);
            tmp = (t.charAt(0) - '0');
            tmp %= k;
            for(int j = 1; j < t.length() ; j++) {
                tmp *= 10;
                tmp += (t.charAt(j) - '0');
                tmp %= k;
            }
            a[i] = tmp;
        }
    }

    public void run() {
        tsp();
    }

    public void tsp() {
        for (int i = 1; i < (1<< n); i++) {
            for (int j = 0; j < k; j++) {
                for(int l = 0; l < n; l++) {
                    if( !isIn(i, l) ) continue;
                    int bf = diff(i, l);
                    if( bf == 0 ) { //요소 하나로만 수열을 만드는 경우
                        dp[i][a[l]] = 1;
                        break;
                    } else {
                        if(dp[bf][j] == 0) continue;
                        int next = j * ten[length[l]];
                        next %= k;
                        next += a[l];
                        next %= k;
                        dp[i][next] += dp[bf][j];
                    }
                }
            }
        }
    }

    public boolean isIn(int subSet, int t) {
        return (subSet & (1 << t)) != 0;
    }

    public int diff(int subSet, int t) {
        return subSet & (~ (1 << t) );
    }

    public String getResult() {
        long numerator = dp[(1<<n)-1][0];
        long denominator = 1;
        for(int i = 2; i <= n; i++) {
            denominator *= i;
        }

        if(numerator == 0)
            return "0/1";

        if(numerator == denominator)
            return "1/1";

        
        long g = gcd(numerator, denominator);

        numerator /= g;
        denominator /= g;

        return numerator + "/" + denominator;
    }
    public long gcd(long a1, long a2) {
        if (a2 == 0) return a1;
        return gcd(a2, a1 % a2);
    }
}

ohj8447 3년 전 0

이번에도 자문자답하게 되었내요

Dp의 자료형이 문제였습니다

최악의 경우 dp는 15!을 가지게 되는데

최악의 값은 대략 1.3076744e+12 의 값이며 이는 int가 가질수 있는 최대값을 상회합니다

해서 해당 자료형을 long으로 변경하여 해결했습니다.

하루를 날려먹었지만 고난이도 문제를 제가 생각한 방법으로 응용해서 풀었기에 즐겁내요

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

문제

문제

출처

ICPC

부가적인 문제가 있는지 확인해주실 수 있나요?

ohj8447 3년 전 1

ohj8447 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말