시간 복잡도 O(N^3)으로 풀더라도 1000000이므로 0.01초로 시간 제한 문제 없음
N개 중 3개를 합한 값이 M이하인 것중 최댓값을 구하는 문제
문제 해결
N[0] + N[1] + N[2] ≤ M → max에 저장
N[0] + N[1] + N[3] ≤ M → max와 비교하여 더 큰 값 max에 저장
...
N[0] + N[1] + N[N.length-1] ≤ M → 더 큰 값 max에 저장
3중 반복문 사용
i = 0 / i < N - 2
j = i + 1 / j < N -1
k = j + 1 / k < N
슈도 코드
N(카드 개수) 저장, M(목표 값) 저장
A(카드를 저장할 배열 선언)
for(0 ~ N-1개 반복){
배열에 카드 값 저장
}
max(최대값을 저장할 변수 선언)
for(i = 0 ~ N-3 반복){
for(j = i+1 ~ N-2 반복){
for(k = j+1 ~ N-1 반복){
tmp = N[i] + N[j] + N[k]
if(tmp <= M && tmp > max){
max = tmp
}
}
}
}
max 출력
코딩하기
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] A = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++){
A[i] = Integer.parseInt(st.nextToken());
}
int max = 0;
for(int i = 0; i < N-2; i++){
if(max == M) break; // max의 값이 M과 같다면 더 이상 비교의 핋요성이 없음
for(int j = i+1; j < N-1; j++){
for(int k = j+1; k < N; k++){
int tmp = A[i] + A[j] + A[k];
if(tmp <= M && tmp > max){
max = tmp;
}
}
}
}
System.out.println(max);
}
