SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
[문제]
숫자게임을 좋아하는 새샘이는 서로 다른 7개의 정수 중에서 3개의 정수를 골라 합을 구해서 수를 만들려고 한다.
이렇게 만들 수 있는 수 중에서 5번째로 큰 수를 출력하는 프로그램을 작성하라.
[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 7개의 서로 다른 정수가 공백으로 구분되어 주어진다. 각 정수는 1이상 100이하이다.
[출력]
각 테스트 케이스마다 첫 번째 줄에는 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 답을 출력한다.
👇 접근방식
7개의 다른 정수 중에 3개의 수를 뽑아서 합을 만드는 문제니,
7C3의 조합으로 35번의 조합만 하면 되는 문제라, dfs로 수 조합을 만들어서 비교를 하면 된다 생각했습니다.
처음에 코드를 짠 코드입니다.
package diff3;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*
5948. 새샘이의 7-3-5 게임 D3
*/
public class Sw_새샘이의735게임 {
static ArrayList<Integer> al;
static boolean[] visited = new boolean[7]; // 7개의 정수
static HashSet<Integer> beforeConvert;
static void dfs(int start, int depth) {
// base case
if (depth == 3) {
permCalc();
}
// recur
for (int i = start; i < al.size(); i++) {
visited[i] = true;
dfs(i + 1, depth + 1);
visited[i] = false;
}
}
private static void permCalc() {
int sum = 0;
for (int i = 0; i < visited.length; i++) {
if (visited[i]) {
sum += al.get(i);
}
}
beforeConvert.add(sum);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
al = new ArrayList<>();
while (st.hasMoreTokens()) {
al.add(Integer.parseInt(st.nextToken()));
}
beforeConvert = new HashSet<>();
dfs(0, 0);
List afterConvert = new ArrayList(beforeConvert);
Collections.sort(afterConvert, Collections.reverseOrder());
System.out.println("#" + (i + 1) + " " + afterConvert.get(4));
}
}
}
위에서 조금 부족한 부분은 dfs 로직을 돈 뒤, base case에서 합 연산을 하는 메서드를 호출하는 게 아니라,
애초에 dfs 내에서 매개변수로 수 연산을 하는 경우로 로직을 변경하면 O(n)에 해당하는 permCalc 메서드가 없어도 됩니다.
import java.io.*;
import java.util.*;
public class Sw_새샘이의735게임_2 {
static HashSet<Integer> hs;
static int[] inputData;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(br.readLine());
inputData = new int[7];
for (int t=1; t<=T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
hs = new HashSet<>();
for (int i=0; i<7; i++) {
inputData[i] = Integer.parseInt(st.nextToken());
}
dfs(0, 0, 0);
List<Integer> sums = new ArrayList<>(hs);
sums.sort(Collections.reverseOrder());
System.out.println("#" + t + " " + sums.get(4));
}
}
private static void dfs (int sum, int depth, int idx) {
if (depth == 3) {
hs.add(sum);
return;
}
for (int i = idx; i < 7; i++) {
dfs(sum + inputData[i], depth+1, i+1);
}
}
}