글 읽기 - 살려주세요.. 반례라도..

laksj113 10달 전 0

30퍼 까진 가긴 하는데

왜 틀렸는지 정말 모르겠습니다.

못 만나면 확률 절반으로 만들어서 보내는 식으로 짰구요

확률은 배열로 해서 배열의 i번째 요소는 2^-i 인 값인 걸로 정했구요

마지막에 각 배열 요소 i의 이전 요소 i-1이 i요소의 2배여서 i요소 2개당 +1을 i-1요소에 더해줬습니다.

제발 제발 반례라도..

import java.util.Queue;

public class _28016 {

    static int N, M;
    static int[] dx = new int[]{1};
    static int[] dy = new int[]{-1, 1};
    static boolean[][] board;
    static boolean[][] visit;
    static ArrayList<ArrayList<int[]>> percent;

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

            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            visit = new boolean[N][M];
            board = new boolean[N][M];
            percent = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                percent.add(new ArrayList<>());
                for (int j = 0; j < M; j++) {
                    percent.get(i).add(new int[101]);
                }
            }

            int start = 0;
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    int cur = Integer.parseInt(st.nextToken());
                    if (cur == 2) {
                        start = i * M + j;
                        visit[i][j] = true;
                        percent.get(i).get(j)[0]++;
                    } else if (cur == 1){
                        board[i][j] = true;
                    }
                }
            }

            bfs(start);

            ArrayList<int[]> arr = percent.get(N-1);

            for (int i = 0; i < M; i++) {
                int[] cur = arr.get(i);
                for (int j = 100; j >= 1; j--) {
                    cur[j-1] += (cur[j] / 2);
                    cur[j] = (cur[j] % 2);
                }
            }

            int[] max = new int[101];
            int idx = -1;

            for (int i = 0; i < M; i++) {
                int[] cur = arr.get(i);
                int n = 0;
                while (n <= 100 && max[n] == cur[n]) {
                    n++;
                }
                if (n <= 100 && max[n] < cur[n]) {
                    max = cur;
                    idx = i;
                }
            }

            bw.write(idx+"");

            bw.flush();
            bw.close();
    }
    
    static void bfs(int start) {
        
        Queue<Integer> q = new LinkedList<>();
        q.add(start);

        while (!q.isEmpty()) {
            
            int cur = q.remove();
            int x = cur / M;
            int y = cur % M;
            int[] per = percent.get(x).get(y);

            if (x+1 < N) {
                // 못을 만난 경우
                if (board[x+1][y]) {

                    for (int i = 0; i < 2; i++) {
                        x += dx[0]; y += dy[i];
                        if (!(y >= M || y < 0 || board[x][y] || board[x-1][y])) {
                            if (!visit[x][y]) {
                                visit[x][y] = true;
                                // 방문 안한 위치만 q에 추가
                                q.add(x*M+y);    
                            }
                            int[] target  = percent.get(x).get(y);
                            // 확률을 반으로 나누어서 추가
                            for (int j = 0; j < 100; j++) {
                                target[j+1] += per[j];
                            }
                        }
                        x -= dx[0]; y -= dy[i];
                    }

                } 
                // 못을 안만난 경우
                else {
                    x++;
                    if (!visit[x][y]) {
                        visit[x][y] = true;
                        q.add(x*M+y);
                    }
                    int[] target  = percent.get(x).get(y);
                    // 확률 그대로 추가
                    for (int j = 0; j <= 100; j++) {
                        target[j] += per[j];
                    }
                }
            }
        }
    }
}

laksj113 10달 전 0

int[] 로 확률을 카운팅 할 때 오버플로가 발생하는 게 문제였습니다.

long[]으로 카운팅 해야 합니다..

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

문제

문제

출처

ICPC

살려주세요.. 반례라도..

laksj113 10달 전 0

laksj113 10달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말