백준 2040 JAVA : 수 게임

문제

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

2040번: 수 게임

 

풀이 예상

현재 위치에서 (내가 먹을 수 있는 값) - (그 다음 턴에서 상대가 최소로 먹을 수 있는 값) 이 최소일 때를 찾아야 한다.

answer가 음수라면 A가 먹은 값보다 B가 먹은 값이 더 큰 것 이므로 A가 이긴다.

 

예를 들어서

nums[] = {10, 7, 2} 라면

1) A 가 2를 선택하면, B는 7을 선택한다. => B가 7을 선택하면 A가 10을 선택한다.

  => (2) - (7 - 10) = 5

2) A가 2, 7을 선택하면, B는 10을 선택한다.

  => (2+7) - 10 = -1

3) A가 2,7,10을 선택하면 B는 0을 선택한다.

  => (2+7+10) - 0 = 19

 

이 중, 제일 적은 2번을 선택한다.

 

풀이방법 (접근 방법 & 시간복잡도)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] nums;
    static int[] sum; //누적 합
    static int[] dp; //메모이제이션 : i 에서 (내 최소합) - (상대의 최소합)이 제일 작은 것
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        N = Integer.parseInt(br.readLine());

        for (int n = 0; n < 3; n++) {
            nums = new int[N+1];
            sum = new int[N+1];
            dp = new int[N+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = N-1; i >= 0; i--) {
                sum[i] = nums[i] + sum[i+1];
            }

            Arrays.fill(dp, Integer.MIN_VALUE);
            
            int answer = find(N-1);
            if(answer < 0) {
                sb.append("A\n");
            }else if(answer > 0) {
                sb.append("B\n");
            }else {
                sb.append("D\n");
            }
        }
        System.out.println(sb);


    }
    static int find(int cur) {
        if(cur < 0) return 0;
        if(dp[cur] != Integer.MIN_VALUE) return dp[cur];

        int temp = Integer.MAX_VALUE;

        for (int i = cur; i >= 0 ; i--) {
            temp = Math.min(temp, sum(cur, i) - find(i-1));
        }
        dp[cur] = temp;
        return dp[cur];
    }
    static int sum(int s, int e) { // s~e 까지의 합
        return sum[e] - sum[s+1];
    }
}

 

결과