백준 10819(차이를 최대로)- Python(파이썬),Java(자바) - 구현,브루트포스(Permutations,Combinations,백트래킹,Java- 스택 사용 )
10819번: 차이를 최대로
첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.
www.acmicpc.net
예제 설명
일단 배열 A를 오름차순으로 정렬한다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 |
| 배열 | 1 | 4 | 8 | 10 | 15 | 20 |
인덱스의 차이가 최대이기 위해서는 고른 인덱스와 선택하지 않은 배열 중 제일 먼 인덱스를 골라야한다.
ex ] 0고르기 -> 5고르기 -> 1고르기 -> 4고르기 -> 2고르기 -> 3고르기
하지만 마지막에 2를 고르고 3을 고르는 것보다 인덱스 3을 제일 앞에 두는 것이 더 차이의 합이 커진다
ex ] 3고르기 -> 0고르기 -> 5고르기 -> 1고르기 -> 4고르기 -> 2고르기
- 처음 인덱스가 0인 경우
인덱스 3 0 5 1 4 2 차이의 합 인덱스의 값 10 1 20 4 15 8 9+19+16
+11+7=62 - 처음 인덱스가 5인 경우
인덱스 2 5 0 4 1 3 차이의 합 인덱스의 값 8 20 1 15 4 10 12+19+14
+11+6=62
이런식으로 둘이 비교하였을 때 최대인 값이 차이의 합이 최대인 62가 나오게 되었다.
N = 6
1. 처음 인덱스가 0인 경우
이 때 고른 인덱스의 경우를 나열하면 ( 3, 0 ), ( 0, 5), ( 5,1 ), ( 1, 4 ), ( 4, 2 ) 이렇게 다섯가지이다. 이 경우를 분류하면
① 인덱스의 합 5(N-1)인 경우 : ( 0, 5 ) ( 1, 4 )
i = 0 -> a[ 5-0 ] - a[ 0 ]
i = 1 -> a [ 5-1 ] - a[ 1 ]
i = 5//2 = 2 -> ( N-1 )을 2로 나눈 몫 전까지 수행
② 인덱스의 합 6(N)인 경우 : ( 5,1 ) ( 4,2 )
i = 1 -> a[ 6-1 ] - a[ 1 ]
i = 2 -> a [ 6-2 ] - a[ 2 ]
i = 6//2 = 3 -> ( N)을 2로 나눈 몫 전까지 수행
③ 예외 : ( 3,0 ) -> 둘의 차이가 3( N//2 )
: a[n//2] - a[0]
2. 처음 인덱스가 5인 경우
이 때 고른 인덱스의 경우를 나열하면 ( 2,5 ), ( 5, 0 ), ( 0, 4 ), ( 4, 1 ), ( 1, 3 )이렇게 다섯가지이다. 이 경우를 분류하면
① 인덱스의 합 5(N-1)인 경우 : ( 5, 0 ) ( 4, 1 )
i = 0 -> a[ 5-0 ] - a[ 0 ]
i = 1 -> a [ 5-1 ] - a[ 1 ]
i = 5//2 = 2 -> ( N-1 )을 2로 나눈 몫 전까지 수행
② 인덱스의 합 4(N -2)인 경우 : ( 0, 4 ) ( 1, 3 )
i = 0 -> a[ 4-1 ] - a[ 1 ]
i = 1 -> a [ 4-2 ] - a[ 2 ]
i = 4//2 = 2 -> ( N-2 )를 2로 나눈 몫 전까지 수행
③ 예외 : ( 2,5 ) -> 둘의 차이가 3( N//2 )
: a[n-1] - a[n-1 - n//2]
=> ①은 공통이고 ②+③의 최대의 값을 찾아서 sum을 구하면 된다.
문제풀이
① 인덱스의 합이 N-1인경우 : 0부터 시작해서 (N-1)//2 전까지 for문으로 a 배열의 차이( a[ n-1 -i ] - a[ i ] )를 더하기
② 인덱스의 합이 N인 경우 : 1부터 시작해서 N//2전까지 for문으로 a배열의 차이( a[n-i] - a[i] )를 더하기
+ ( a[ n// 2 ] - a[ 0 ] )
③ 인덱스의 합이 N-2인 경우 : 0부터 시작해서 (N-2)//2전까지 for문으로 a배열의 차이( a[ n-2-i ] - a[ i ] )를 더하기
+ ( a[n-1] - a[ n-1 - n//2 ] )
④ ②,③의 경우를 비교하여서 큰 값을 ①을 더하기
💻Python(파이썬)
import sys
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
#정렬
a.sort()
sum=num1=num2 =0
#1.인덱스의 합이 N-1인 경우
for i in range((n-1)//2):
sum+=a[n-1-i]-a[i]
#2.인덱스의 합이 합이 N인 경우
for i in range(1,n//2):
num1 += a[n-i]-a[i]
num1 += a[n//2]-a[0]
#3.인덱스의 합이 N-2인 경우
for i in range(1,(n-2)//2):
num2 += a[n-2-i]-a[i]
num2 += a[n-1]-a[n-1-n//2]
#2번과 3번 비교
if num1>num2:
sum+=num1
else:
sum+=num2
print(sum)💻 Java(자바)
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());
StringTokenizer st = new StringTokenizer(br.readLine()," ");
int[] a = new int[n];
for(int i=0;i<n;i++){
a[i]=Integer.parseInt(st.nextToken());
}
Arrays.sort(a);
int sum =0;
for(int i=0;i<(n-1)/2;i++){
sum+=a[n-1-i]-a[i];
}
int num1=0,num2=0;
for(int i=1;i<n/2;i++){
num1 += a[n-i]-a[i];
}
num1 += a[n/2]-a[0];
for(int i=0;i<(n-2)/2;i++){
num2+= a[n-2-i]-a[i];
}
num2 += a[n-1]-a[n-1-n/2];
if(num1>num2){
sum+=num1;
}else{
sum+=num2;
}
System.out.println(sum);
}
}📌 파이썬 Permutation 사용
Python( 파이썬 )
참고 자료 : https://velog.io/@dramatic/Python-permutation-combination-순열과-조합
📖 permutations : 순열 라이브러리(nPr)
- 서로 다른 n개 중에서 r개를 골라 순서를 나열하는 가짓수
from itertools import permutations
arr = [ 'A', 'B', 'C' ]
#('A', 'B', 'C') ('A', 'C', 'B') ('B', 'A', 'C') ('B', 'C', 'A') ('C', 'A', 'B') ('C', 'B', 'A')
nP3 = permutations(arr) #arr의 가짓수
#('A', 'B') ('A', 'C') ('B', 'A') ('B', 'C') ('C', 'A') ('C', 'B')
nP2 = permutations(arr,2) #arr에서 2개의 원소를 골라 나열하는 가짓수
#('A')('B')('C')
nP1 = permutations(arr,1) #arr에서 1개의 원소를 골라 나열하는 가짓수📖 combinations : 조합 라이브러리(nCr)
- 서로 다른 n개 중에서 r개를 뽑는 경우의 수
- 조합의 경우는 순서를 신경쓰지 않고 누구를 뽑았는지 중요
from itertools import combinations
arr = [ 'A', 'B', 'C' ]
#('A', 'B', 'C')
nC3 = combinations(arr,3) #arr의 가짓수
#('A', 'B') ('A', 'C') ('B', 'C')
nC2 = combinations(arr,2) #arr에서 2개의 원소를 고르는 가짓수
#('A')('B')('C')
nC1 = combinations(arr,1) #arr에서 1개의 원소를 고르는 가짓수
for i in nC3:
print(i,end=" ")
for i in nC2:
print(i,end=" ")
for i in nC1:
print(i,end=" ")문제 풀이
① 배열이 나열 될 수 있는 전체 가짓수 n!를 저장
② 입력 받은 배열을 하나씩 차이의 sum 값을 계산하고 전에 구한 값보다 지금 구한 sum값이 클 경우 변경
③ 최종 최댓값 출력
💻 Python(파이썬) - Permutation 라이브러리 사용
import sys
#순열
from itertools import permutations
n = int(sys.stdin.readline())
array = list(map(int,sys.stdin.readline().split()))
#배열의 가짓수
nPr = permutations(array)
#가장 큰 배열 초기화
max_sum=0
#배열마다 하나씩 실행
for arr in nPr:
sum=0
#배열 하나마다 차이의 sum 값 구하기
for j in range(len(arr)-1):
sum+=abs(arr[j]-arr[j+1])
#만약 전에 구한 값보다 지금 구한 sum이 크면
if max_sum<sum:
max_sum = sum
print(max_sum)📌 Permutation 사용하지 않고 백트래킹으로 구하기
문제 풀이
① 백트래킹 함수(x) 함수를 구현
- temp : 인덱스 숫자를 담는 배열 ( ex. [0 1 2 3] -> 0,1,2,3 인덱스 )
- x : 백트래킹 함수의 인수로 temp에 담긴 개수는 x을 의미
- if x==n 은 temp에 모든 숫자가 담겼다는 의미로 배열[temp의 숫자]를 for문으로 돌려서 차이의 합을 구해야한다
이 값이 전에 값이랑 비교해서 큰 경우 답에 적기
백트래킹은 이해가 되었는데 코드를 봤더니 이해가 되지 않아서 코드 하는 방법을 좀 적어보았다.
부연 설명 펼쳐보기
1. sol[0]를 실행해서 [0]을 집어넣고 pop을 하기 전에 재귀함수를 호출해서 sol[0+1]를 호출
2. sol[1]를 실행해서 [0 1]을 집어넣고 pop을 하기 전에 재귀함수를 호출해서 sol[1+1]를 호출
3. sol[2]를 실행해서 [0 1 2]을 집어넣고 pop을 하기 전에 재귀함수를 호출해서 sol[2+1]를 호출
4.sol[3]를 실행해서 [0 1 2 3]을 집어넣고 pop하기 전에 재귀함수를 호출해서 백트래킹 함수(sol[3+1])를 호출
5.sol[4]를 실행해서 [0 1 2 3 4]을 집어넣고 pop하기 전에 재귀함수를 호출해서 백트래킹 함수(sol[4+1])를 호출
6.sol[5]를 실행해서 [0 1 2 3 4 5]을 집어넣고 pop하기 전에 재귀함수를 호출해서 백트래킹 함수(sol[5+1])를 호출
7.sol[6]을 실행하는데 6==N이랑 동일하므로 if문 실행해서 차이를 구하고 종료 -> sol[5]의 pop 하러 가기
8. sol[5] pop을 하였기에 [0 1 2 3 4]하고 종료 -> sol[4]의 pop하러가기
9.sol[4]의 pop을 하였기에 [0 1 2 3]하고 i=5하기 -> i=5가 없기에 5를 집어넣고 [0 1 2 3 5] 재귀함수 호출해서 sol[4+1] 호출
10. sol[5]를 실행하는데 i=4 인덱스가 없으므로 [0 1 2 3 5 4]로 append하고 pop하기 전에 재귀함수 sol[5+1]을 호출
11.so[6]을 실행하는데 6==N이랑 동일하므로 If문 실행해서 아까 7번에서 구한 값과 비교하여 큰값을 저장 -> sol[5] pop하러 가기
12. sol[5]의 pop을 하였기에 [0 1 2 3 5]에서 i=5를 실행하는데 이미 인덱스 5가 있으므로 종료
13. sol[3]의 pop을 하여서 [0 1 2 3]에서 i=4 실행
..........
코드 참고 자료 : https://fre2-dom.tistory.com/442
💻 Python(파이썬) - Permutation 라이브러리 사용하지 않고 재귀함수 백트래킹
import sys
def sol(x):
global answer
# x가 n개라면 => x == len(temp)
# 조건에 맞게 수를 더해준다.
if x == n:
total=0
#차이의 합을 구하기
total = sum(abs(m[temp[i + 1]] - m[temp[i]]) for i in range(n - 1))
#이전에 구한 합과 비교해서 큰값을 저장
answer = max(total,answer)
return
# 반복문을 통해 idx를 temp에 저장
for i in range(n):
if i not in temp:
temp.append(i)
sol(x + 1) # 백 트래킹
temp.pop()
n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
#차이의 합
answer = 0
#배열의 인덱스의 값
temp = []
sol(0)
print(answer)💻 Java(자바) -> Python과 동일한 방법으로 temp를 pop 사용
참고 자료 : https://wakestand.tistory.com/197
* 스택 선언 - Stack<Integer> temp = new Stack<Integer>();
* 스택 인덱스 확인 temp.elementAt(i) : i번째 인덱스 확인
* 스택 안에 특정 값있는지 확인 temp.indexof(i): i가 스택안에 들었는지 확인
* 스택 안에 넣기 temp.push(i) -> 스택 temp안에 i 넣기
import java.util.*;
import java.io.*;
public class Main {
static int sum =0;
static int n;
static int[] array;
static Stack<Integer> temp = new Stack<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
array = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<n;i++){
array[i] = Integer.parseInt(st.nextToken());
}
sol(0);
System.out.println(sum);
}
static void sol(int x){
if(x==n){
int total = 0;
for(int i=0;i<n-1;i++){
//스택 인덱스 확인
total += Math.abs(array[temp.elementAt(i+1)]- array[temp.elementAt(i)]);
}
if(total>sum){
sum = total;
}
return;
}
for(int i=0;i<n;i++){
if(!temp.contains(i)){
temp.push(i);
sol(x+1);
temp.pop();
}
}
}
}💻 Java(자바) -> visted로 포함한 함수인지 확인하는 법
import java.util.*;
import java.io.*;
public class Main {
static int sum =0;
static int n;
static int[] array,temp;
static boolean[] visted;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
array = new int[n];
temp = new int[n];
visted=new boolean[n];
StringTokenizer st = new StringTokenizer(br.readLine()," ");
for(int i=0;i<n;i++){
array[i] = Integer.parseInt(st.nextToken());
}
sol(0);
System.out.println(sum);
}
static void sol(int x){
if(x==n){
int total = 0;
for(int i=0;i<n-1;i++){
total += Math.abs(array[temp[i+1]]- array[temp[i]]);
}
if(total>sum){
sum = total;
}
return;
}
for(int i=0;i<n;i++){
if(!visted[i]){
visted[i]=true;
temp[x]=i;
sol(x+1);
visted[i]=false;
}
}
}
}