[JAVA] 백준 2303_숫자게임

 

[문제링크]

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

 

 

📌 문제 탐색하기

모든 사람의 카드 조합중에서 세장을 선택하고 그 합의 일의자리 숫자가 가장 큰 값을 찾는 문제이다.

만약, 최대 값이 여러명인 경우는 번호가 가장 큰 사람의 번호를 출력하는 문제이다. 

 

📌 가능한 시간복잡도 

각각 사람들은 5장의 카드를 가지고 있고 이중에 3장의 카드를 선택해야하는거니까 조합으로 계산하면 10의 조합을 확인해야한다는거임. 입력받은 사람 N명 - 각각 10번의 계산을 진행해야하는거니까 총 연산은 O(N * 10) 이라고 생각함.

 

따라서, 가능한 시간복잡도는 O(N * 10)입니다.

 

📌 코드 설계하기

1. 입력하기 : 사람의 수 N 입력받기

                     입력받은 N명의 사람 수 만큼 5장의 카드를 각각 입력받기

2. 각 사람의 카드에서 3장을 선택해서 가능한 조합 만들어서 체크

3. 각각 조합의 합의 일의자리 숫자를 구해서 조합의합 % 10 연산처리

4. 일의 자리 최대인 값 찾기 : 각 사람의 조합에서 최대 일의 자리 값을 구하고 최대 일의 자리 값을 기준으로 승자 출력 ( 만약에 동일한 최대 값이 있는 경우 번호가 가장 큰 사람이 승자로 출력된다. )

 

📌 정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); 
        int winner = 0; 
        int maxRemainder = -1; 
        for (int i = 1; i <= N; i++) {
            String[] input = br.readLine().split(" ");
            int[] cards = Arrays.stream(input).mapToInt(Integer::parseInt).toArray();
            
            int maxCurrent = 0;
            for (int a = 0; a < 5; a++) {
                for (int b = a + 1; b < 5; b++) {
                    for (int c = b + 1; c < 5; c++) {
                        int sum = cards[a] + cards[b] + cards[c];
                        int remainder = sum % 10;
                        maxCurrent = Math.max(maxCurrent, remainder);
                    }
                }
            }
            if (maxCurrent > maxRemainder || (maxCurrent == maxRemainder && i > winner)) {
                maxRemainder = maxCurrent;
                winner = i;
            }
        }
        System.out.println(winner);
    }
}