백준 2303 숫자 게임

문제

설명

dfs와 같이 재귀를 활용해서 전체를 탐색하도록 푸는 아이디어로 접근했다.

첫번째 간과했던 점은 같은 점수면 index가 높은 값을 구해야 했고,

두번째 간과했던 점은 재귀를 돌 때에 left, center, right와 같이 3개로 나누어서 구현했는데

right가 4까지 도달하면 center를 움직이고 left를 움직였다.

하지만 이렇게 되면 예제 케이스를 통과하지 못한다. 왜냐하면 5 5 9를 선택해야 하는데 left보다 center를 먼저 움직이면 5 5 9를 선택하지 못하기 때문이다. 그래서 right 다음에 left를 움직이고 마지막에야 center를 움직여서 처리했다. 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    // 2303 숫자 게임
    public static void main(String[] args) throws IOException {
        process();
    }

    static int[] arr = new int[5];
    static int tempValue = -1;
    private static void process() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int maxUserIndex = -1;
        int maxUserValue = -1;
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 5; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }
            
            recursive(0, 1, 2);

            if(maxUserValue <= tempValue) {
                maxUserValue = tempValue;
                maxUserIndex = i+1;
            }
            tempValue = 0;
        }

        bw.write(maxUserIndex + "");
        bw.flush();
        bw.close();
    }

    private static void recursive(int left, int center, int right) {
        int sum = (arr[left] + arr[center] + arr[right]) % 10;
        tempValue = Math.max(sum, tempValue);

        if(right + 1 < 5) {
            recursive(left, center, right+1);
        } else if(left+1 < center) {
            recursive(left+1, center, right);
        } else if(center + 1 < right) {
            recursive(left, center + 1, right);
        }
    }
}