문제 풀이(64)

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

import java.util.*;
import java.io.*;

/*
3
7 5 5 4 9
1 1 1 1 1
2 3 3 2 10
 */
class Node implements Comparable<Node>{
    int idx;
    int value;

    Node(int idx , int value){
        this.idx = idx;
        this.value = value;
    }

    @Override
    public int compareTo(Node n){

        if (this.value == n.value) {
            return n.idx - this.idx;
        }

        return n.value - this.value;
    }
}


class Main {
    
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();

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

        dfs(0,0 ,new ArrayList<>(), new HashSet<>());

        

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  

        int num = Integer.parseInt(br.readLine());

        ArrayList<Node> ans = new ArrayList<>();

        for (int i = 0; i < num; i++) {
            
            StringTokenizer st = new StringTokenizer(br.readLine());

            ArrayList<Integer> A= new ArrayList<>();

            for (int j = 0; j < 5; j++) {
                

                A.add(Integer.parseInt(st.nextToken()));

            }

            //System.out.println(A);

            int max = 0;

            for(ArrayList<Integer> key : list)
            {
                int sum = 0;

                for(int now : key)
                {
                    sum += A.get(now);
                }

                String s = String.valueOf(sum);

                s = s.substring(s.length() - 1);

                int temp = Integer.parseInt(s);

                if (temp > max) {
                    max = temp;
                }
            }

            ans.add(new Node(i + 1, max));

        }


        Collections.sort(ans);

        System.out.println(ans.get(0).idx);
        
    }

    public static void dfs(int k,int index  ,ArrayList<Integer> result , HashSet<Integer>set){

        if (k == 3) {
            
            ArrayList<Integer>data = new ArrayList<>(result);

            list.add(data);

            return;
        }


        for (int i = index; i < 5; i++) {
            if(set.contains(i))continue;
            result.add(i);set.add(i);
            dfs(k + 1, i, result, set);
            result.remove(result.size() - 1); set.remove(i);
        }

    }
}

문제 풀이 방법

각 카드에는 1부터 10 사이의 숫자가 적혀 있습니다. 게임의 목표는 참가자들이 자신의 카드 중 3장을 선택하여, 그 합의 일의 자리 숫자가 가장 큰 사람을 찾는 것입니다. 만약 가장 큰 일의 자리 숫자를 가진 사람이 여러 명일 경우, 그 중 번호가 가장 큰 사람이 승자가 됩니다.

프로그램은 다음과 같은 방식으로 작동합니다:

Node 클래스: 이 클래스는 참가자의 인덱스(idx)와 그 참가자가 선택한 카드 3장의 합의 일의 자리 숫자(value)를 저장합니다. compareTo 메소드는 우선 value를 기준으로 내림차순 정렬을 수행하며, value가 같을 경우 idx를 기준으로 내림차순 정렬을 합니다. 이는 최대 일의 자리 숫자를 가진 사람을 찾되, 같은 값일 경우 번호가 큰 사람을 선택하기 위함입니다.

dfs 메소드: 이 메소드는 깊이 우선 탐색(DFS) 알고리즘을 사용하여 가능한 모든 3장 카드의 조합을 찾습니다. 각 조합은 list라는 전역 변수에 저장됩니다.

Main 알고리즘: 사용자로부터 참가자 수(num)와 각 참가자의 카드가 입력됩니다. 각 참가자에 대해, 모든 카드 조합을 순회하며 가능한 가장 큰 일의 자리 숫자를 계산합니다. 계산된 최대값을 가진 Node 객체가 ans 리스트에 추가됩니다.

결과 출력: ans 리스트는 Node 객체의 compareTo 메소드를 사용하여 정렬되며, 이후 승자의 인덱스(즉, 게임에서 이긴 사람의 번호)가 출력됩니다.