[Java] baekjoon_14494 : 다이나믹이 뭐예요?

다이나믹 프로그래밍

다이나믹이 뭐예요? : Silver3

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

14494번: 다이나믹이 뭐예요?

 

 

 

풀이

import java.io.*;
import java.math.BigInteger;

public class Main {
    static final BigInteger MOD = BigInteger.valueOf(1000000007);

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 공백으로 구분된 입력을 받아오기
        String[] input = br.readLine().split("\\s+");

        // 각각의 문자열을 BigInteger로 변환
        BigInteger n = new BigInteger(input[0]);
        BigInteger m = new BigInteger(input[1]);

        // 결과 계산
        BigInteger ret = countCases(n, m);

        // 결과 출력
        bw.write(ret.mod(MOD).toString());
        bw.newLine();
        bw.flush();
        bw.close();
        br.close();
    }

    static BigInteger countCases(BigInteger n, BigInteger m) {
        // BigInteger 배열을 초기화
        BigInteger[][] dp = new BigInteger[n.intValue() + 1][m.intValue() + 1];
        for (int i = 0; i <= n.intValue(); i++) {
            for (int j = 0; j <= m.intValue(); j++) {
                dp[i][j] = BigInteger.ZERO;
            }
        }

        // 초기값 설정
        dp[1][1] = BigInteger.ONE;

        // 다이나믹 프로그래밍 진행
        for (int i = 1; i <= n.intValue(); i++) {
            for (int j = 1; j <= m.intValue(); j++) {
                if (i == 1 && j == 1) {
                    continue;
                }
                dp[i][j] = dp[i][j].add(dp[i - 1][j]).add(dp[i][j - 1]).add(dp[i - 1][j - 1]);
                dp[i][j] = dp[i][j].mod(MOD);
            }
        }

        return dp[n.intValue()][m.intValue()];
    }
}

 

ㄴ java.math.BigInteger 를 이용하였다.

ㄴ BigInteger의 add와 mod 메서드를 이용하였다.

ㄴ 다이나믹 프로그래밍 진행

• 중첩된 반복문을 사용하여 각 위치 (i, j)에서의 경우의 수를 계산한다.
• 시작점은 이미 (1, 1)로 초기화하고, (1, 1)부터 (n, m)까지의 모든 위치에 대해 경우의 수를 계산한다.
• 현재 위치의 경우의 수는 왼쪽, 위쪽, 대각선 위 방향의 경우의 수를 합하여 계산된다.
• 계산된 값에 대해 MOD로 나눈 나머지를 다시 저장한다.

 

 

java.math.BigInteger

BigInteger를 사용하는 이유는 정수 오버플로우를 방지하기 위해서이다. 

 

일반적인 정수형 변수(int 또는 long)는 특정 범위 내에서만 값을 표현할 수 있다.

예를 들어, int는 대략 -2^31부터 2^31-1까지의 값을 표현할 수 있다.

 

만약 연산 결과가 이 범위를 초과하면 정수 오버플로우가 발생하여 부정확한 결과가 나올 수 있다. 그래서 위 문제에서 dp를 int로 선언했을 때 오버플로우가 발생하여 결과값이 음수로 출력된 것이다.
반면에 BigInteger는 임의의 정밀도 정수 산술을 지원하므로 매우 큰 값도 다룰 수 있다. 따라서 BigInteger를 사용하면 정수 오버플로우를 방지하고 더 넓은 범위의 값을 다룰 수 있다.

특히, 위 문제에서는 중간에 발생하는 계산 과정에서 값이 매우 커질 수 있으므로 BigInteger를 사용하여 정밀도를 높였다. 또한, 결과를 나머지로 나누어야 했기 때문에 BigInteger의 mod 메서드를 사용하여 나머지를 효과적으로 처리하였다.

 

BigInteger의 상수

BigInteger.ZERO : 값이 0인 BigInteger 상수
BigInteger.ONE : 값이 1인 BigInteger 상수

 

이러한 상수들은 BigInteger 클래스에 미리 정의되어 있어서, 0 또는 1을 나타내는 BigInteger를 생성할 때 매번 새로운 객체를 생성할 필요 없이 사용할 수 있다.

 

예를 들어, BigInteger.ZERO는 new BigInteger("0")과 동일하게 동작하지만, 상수를 사용하는 것이 편리하고 가독성이 좋다.

 

BigInteger의 intValue()

BigInteger 클래스의 메서드로, 해당 BigInteger 값을 int로 변환한다.
이 메서드는 BigInteger 객체가 나타내는 정수 값이 int의 표현 범위 내에 있을 때 사용된다.
BigInteger는 임의의 정밀도 정수를 나타내기 때문에 매우 큰 값도 다룰 수 있지만 특정 상황에서는 int로 충분한 경우가 있다.

따라서 intValue()를 사용하여 BigInteger를 int로 변환하여 사용할 수 있습니다.

 

 

---

 

 

문제점 : 1000 1000 입력 시 오버플로우가 발생하여 음수가 출력됐다.

해결 방법 : BigInteger 를 이용하여 오버플로우를 방지하였다.

깨달은 바 : 입력 값을 통해 출력되는 값의 크기가 너무 클 경우 발생하는 오버플로우에 대해 신경을 쓰며 문제를 풀어야겠다는 생각이 들었다.