👩‍💻 BOJ_1026_보물

💬 처음에 조합을 통해 모든 경우의 수를 구한 뒤 최소값을 계산하는 방식으로 문제를 해결했으나, 시간초과가 발생했습니다.
최소값만 구하는 문제이니 두 배열을 오름/내림차순 으로 정렬하여 식에 적용시키는 방안으로 변경하여 해결했습니다.
비록 틀렸지만 순열에 대해 공부하는 시간 을 가질 수 있어 의미있었습니다.

📄 문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

💡 풀이 방법

• A, B 배열을 저장합니다.
• A, B 배열을 정렬합니다.
• 제일 작은 수 * 제일 큰 수 + ... + (제일 작은 수 + 1) * (제일 큰 수 -1) 로 계산합니다.
• 계산된 값을 출력합니다.

🔥 코드

import java.util.Arrays;
import java.util.Scanner;

public class 선물 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); 
		
		// 저장소 선언 
		int a[] = new int[N];
		int b[] = new int[N];
		
		// 배열에 저장
		for(int n = 0; n < N; n++) {
			a[n] = sc.nextInt();
		}
		for(int n = 0; n < N; n++) {
			b[n] = sc.nextInt();
		}

		// a 정렬 
		Arrays.sort(a);
		
		// b 정렬
		Arrays.sort(b);
		
		// 제일 작은 값 계산
		int result = 0;
		for(int i = 0; i < N; i++) {
			result += a[i] * b[N-i-1];
		}
		
		// 정답 표시
		System.out.println(result);
	}
}

// 순열로 풀 경우, 시간초과가 발생했다. 
/*
public class 선물 {
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); 
		
		// 저장소 선언 
		int a[] = new int[N];
		int b[] = new int[N];
		
		// 배열에 저장
		for(int n = 0; n < N; n++) {
			a[n] = sc.nextInt();
		}
		for(int n = 0; n < N; n++) {
			b[n] = sc.nextInt();
		}

		// a 순서 바꿀 수 있는 경우 저장 (순서가 상관 없으니 조합)
		per(a, b, 0, N, N);
		
		// 제일 작은 값 추출 (추출)
		System.out.println(min);
	}
	
	static void per(int[] a, int[] b, int depth, int n, int r) {
		if(depth == r) {
			// 경우의 수에 맞게 계산
			int result = 0; 
			
			for(int i = 0; i < n; i++) {
				result += a[i] * b[i]; 
			}
			
			// 값 저장
			if(result < min) {
				min = result;
			}
			return;
		}

		for(int i = depth; i < n; i++) {
			swap(a, depth, i);
			per(a, b, depth + 1, n, r);
			swap(a, depth, i);
		}
	}
	
	// 순서를 바꿔주는 함수
	static void swap(int[] a, int depth, int i) {
		int tmp = a[depth];
		a[depth] = a[i];
		a[i] = tmp;
	}

}
*/

⭐️ 오늘의 학습

순열 in Java : swap 이용하기

1. 배열의 처음부터 다음 값과 순서를 바꾸면서 새로운 조합을 만든다.
2. 기준 인덱스를 설정하고 기준 보다 작은 값들은 고정하고 큰 값들은 순서를 변경한다.