BOJ28016 경품추첨(Java)

---

https://www.acmicpc.net/problem/28016

태그 : dp, 임의 정밀도/큰 수 연산

---

사고 과정

아이디어는 전혀 어려울 것이 없다. 소수점 문제만 아니면 골드 하위까지 내려가도 되지 않을까 싶다.

그냥 2차원 dp를 위에서부터 갱신하면 된다.

다만 문제를 잘못 읽으면 실수할 수도 있는게,

공의 이동이 오른쪽으로 한칸 이동 후 아래로 가는 것임을 인지해야 한다.

---

소수 계산

dp값을 double로 설정했다. 최대 2^(-100) 까지 내려가니까 문제가 생길 것이라고 생각했고,

처음에 gemini한테 물어봤을 때는 문제 없을 것이라고 알려주었다.

하지만 WA를 받았고, 역시 소수 연산은 가능한 피하는 것이 맞다는 생각이 들었다.

그래서 Java의 BigInteger로 그냥 2^100을 2씩 나누면서 dp값을 정수로 바꾸었다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static int [][] board = new int[100][100];
    static BigInteger[][] dp = new BigInteger[100][100];
    static int N, M;

    public static void solve() {
        for (int i = 0 ; i < N; ++i) {
            for(int j = 0; j < M; j++) {
                dp[i][j] = BigInteger.ZERO;
            }
        }

        for (int i = 0 ; i < M; ++i) {
            if (board[0][i] == 2) {
                dp[0][i] = new BigInteger("2").pow(100);
                break;
            }
        }

        for (int i = 0 ; i < N - 1; ++i) {
            for (int j = 0 ; j < M; ++j) {
                if (dp[i][j].equals(BigInteger.ZERO)) {
                    continue;
                }
                if (board[i + 1][j] == 0) {
                    dp[i + 1][j] = dp[i + 1][j].add(dp[i][j]);
                }
                else {
                    boolean checkRight = (j + 1 < M && board[i][j + 1] != 1 && board[i + 1][j + 1] != 1);

                    boolean checkLeft = (j - 1 >= 0 && board[i][j - 1] != 1 && board[i + 1][j - 1] != 1);

                    BigInteger half = dp[i][j].divide(BigInteger.valueOf(2));

                    if (checkRight && checkLeft) {
                        dp[i + 1][j + 1] = dp[i + 1][j + 1].add(half);
                        dp[i + 1][j - 1] = dp[i + 1][j - 1].add(half);
                    }
                    else if (checkRight) {
                        dp[i + 1][j + 1] = dp[i + 1][j + 1].add(half);
                    }
                    else if (checkLeft) {
                        dp[i + 1][j - 1] = dp[i + 1][j - 1].add(half);
                    }
                }
            }
        }
        BigInteger max = BigInteger.ZERO;
        int idx = -1;
        for (int i = 0; i < M; ++i) {
            if (dp[N - 1][i].compareTo(max) > 0) {
                max = dp[N - 1][i];
                idx = i;
            }
        }
        sb.append(idx);
    }

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

        st = new StringTokenizer(br.readLine().trim());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        for (int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 0 ; j < M ; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        solve();

        System.out.println(sb);
    }
}

---

후기

소수 연산은 진짜 최대한 배제해야겠다고 생각했다.

Java는 BigInteger 클래스 있어서 구현이 쉬웠다.

C++에서는 BigInteger를 구현하거나 해야할 것 같다.