새샘이의 7-3-5 게임

17 Jul 2020 in Algorithm on SW Expert Academy

SW Expert Academy 5948: 새샘이의 7-3-5 게임

문제보기
Alt text

풀이

재귀함수를 이용하여 조합을 구현
3개 정수의 합을 구하여 리스트에 담을 때 중복하는 값이 있으면 담지 않음을 주의
리스트를 내림차순으로 정렬 -> Collections.sort(리스트명, Collections.reverseOrder());

소스코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++) {
            int[] arr = new int[7];
            list = new ArrayList<>();
            for(int i=0; i<7; i++)
                arr[i] = sc.nextInt();
            //조합
            combi(arr, 0, 0, new int[3]);
             
             //리스트 정렬(내림차순)
            Collections.sort(list, Collections.reverseOrder());
            System.out.println("#"+tc+" "+list.get(4));
        }
    }
    static ArrayList<Integer> list;
    static void combi(int[]arr, int n, int c, int[] sel) {
        if(c==sel.length) {
            //합 구해서 배열에 담기
            int sum = 0;
            for(int i=0; i<3; i++) {
                sum += sel[i];
            }
            if(!list.contains(sum))
                list.add(sum);
            return;
        }
        if(n==arr.length)
            return;
         
        sel[c] = arr[n];
        combi(arr, n+1, c+1, sel);
        combi(arr, n+1, c, sel);
    }
}