글 읽기 - 어디서 틀렸는지 잘 모르겠습니다(정답코드)

pmn0001 2년 전 0

현재까지 세운 학생들을 비트로 체크하고, 바로 직전에 세운 학생의 인덱스를 함수 인자로 설정했습니다

어디가 문제일까요ㅠㅠ

(맨 처음엔 키가 9999999인 가상의 학생을 세우는것으로 처음 학생의 키가 어떻든 경우의수를 따지게 했습니다)

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

public class Main {
    static int n,k,kind;
    static int[] height;
    static int[][] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        height = new int[n+1];
        for(int i=0; i<n; i++){
            height[i] = Integer.parseInt(br.readLine());
        }
        height[n] = 9999999;

        kind = (int)Math.pow(2,n);
        dp = new int[kind][n+1];
        for(int i=0; i<kind; i++){
            Arrays.fill(dp[i], -1);
        }

        System.out.println(func(0, n));
    }
    static int func(int students, int beforeStudent){
        if(dp[students][beforeStudent] != -1) return dp[students][beforeStudent];
        if(students == kind-1) return 1;

        int ret=0;
        for(int i=0; i<n; i++){
            if(((students & (1<<i))!=0) || (Math.abs(height[beforeStudent]-height[i]) <= k)) continue;

            ret += func(students | (1<<i), i);
        }
        dp[students][beforeStudent] = ret;
        return dp[students][beforeStudent];
    }
}

pmn0001 2년 전 0

해결했습니다.

답이 int범위를 벗어날 수 있다는 것을 생각 못했었습니다

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

문제

문제

출처

ICPC

어디서 틀렸는지 잘 모르겠습니다(정답코드)

pmn0001 2년 전 0

pmn0001 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말