백준 9358번

문제 9358번

풀이접근

1. 정수 n을 입력 받는다.
2. 승자를 저장하는 winner[n] 배열을 boolean[] 타입으로 만든다.
3. 숫자가 2개만 남을 때까지 접는 작업을 반복하는 재귀함수인 Fold함수를 구현한다.
4. Fold함수에서 얻어진 배열을 입력으로 boolean 값을 출력 받아 boolean 값을 반환하는 whowhin함수를 구현하여 winner[] 배열에 저장한다.
5. winner가 true일 때 Alice를 false일 때 Bob을 출력하게 조건문을 작성하여 결과를 출력한다.

소스코드

import java.io.*;
public class boj9358 {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        boolean[] winner = new boolean[t];
        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(br.readLine());
            String[] input1 = br.readLine().split(" ");
            int[] input = new int[input1.length];
            for (int j = 0; j < n; j++) {
                input[j] = Integer.parseInt(input1[j]);
            }
            winner[i] = whowin(Fold(input));
        }
        for (int i = 0; i < t; i++) {
            System.out.printf("Case #%d: ", i+1);
            if(winner[i]){
                System.out.printf("Alice\n");
            }else{
                System.out.printf("Bob\n");
            }
        }
    }
    public static int[] Fold(int[] arr){
        if(arr.length == 2){
            return arr;
        }
        if(arr.length %2 != 0){
            int n = (Math.round((float)arr.length / (float) 2));
            int[] res = new int[n];
            for (int i = 0; i < n - 1; i++) {
                res[i] = arr[i] + arr[arr.length -i-1];
            }
            res[n-1] = arr[n-1] *2;
            return Fold(res);
        }else{
            int n = arr.length/2;
            int[] res = new int[n];
            for (int i = 0; i < n - 1; i++) {
                res[i] = arr[i] + arr[arr.length-1-i];
            }
            return Fold(res);
        }
    }
    public static boolean whowin(int[] arr){
        return (arr[0] > arr[1]);
    }
}

문제핵심

• Fold 함수를 구현 할 수 있는가
• 메소드를 통해 메모리를 절약할 수 있는가
  (나는 단순 main 코딩으로 메모리 초과를 2번 받았다)