BOJ(백준) 10819[차이를 최대로]

안녕하세요! 오늘은 백준의 10819번 문제인 “차이를 최대로” 문제를 함께 풀어보겠습니다. 이 문제는 주어진 수열에서 인접한 원소의 차의 절댓값의 합을 최대로 만드는 문제입니다.

1. 문제 설명

1) 문제 개요
• 주어진 수열을 이용하여 인접한 원소의 차의 절댓값의 합을 최대로 만드는 순열을 찾아야 합니다.
• 주어지는 수열의 길이  N 은 3 이상 8 이하입니다.
2) 입력
• 첫 줄에 수열의 길이  N 이 주어집니다.
• 두 번째 줄에 수열  A 가 주어집니다.
3) 출력
• 인접한 원소의 차의 절댓값의 합 중 최댓값을 출력합니다.

 

문제URL : https://www.acmicpc.net/problem/10819

 

2. 접근법

1) 입력받기
• sys.stdin.readline을 사용하여 입력 속도를 높입니다.
• 첫 번째 줄에서  N (수열의 길이)을 입력받고, 두 번째 줄에서 수열  A 를 입력받습니다.
2) 백트래킹을 이용한 순열 생성
• 순열을 생성하여 각 순열에 대해 인접한 원소의 차의 절댓값의 합을 계산합니다.
• 최대 합을 저장하기 위해 ans 변수를 사용합니다.
3) 순열의 차이 합 계산
• 각 순열에 대해 인접한 원소의 차의 절댓값의 합을 계산하여 최대 값을 갱신합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력 받기
N = int(input())  # 수열의 길이
A = list(map(int, input().split()))  # 수열

# 전역 변수 초기화
tmp = []                # 현재 순열을 저장하는 리스트
visit = [False] * N     # 각 원소의 방문 여부를 저장하는 리스트
ans = 0                 # 최대 합을 저장하는 변수

# 백트래킹 재귀 함수 정의
def recur(idx):
    global tmp
    global ans
    global visit
    
    # 모든 원소를 사용하여 순열을 만든 경우
    if idx == N:
        # 현재 순열에서 인접한 원소의 차의 절댓값의 합 계산
        total = sum(abs(tmp[i] - tmp[i+1]) for i in range(N-1))
        # 최대 합 갱신
        ans = max(total, ans)
        return
    
    # 수열의 모든 원소를 하나씩 시도
    for i in range(N):
        # 해당 원소를 아직 사용하지 않은 경우
        if not visit[i]:
            visit[i] = True     # 현재 원소 사용 표시
            tmp.append(A[i])    # 현재 원소를 순열에 추가
            recur(idx + 1)      # 다음 인덱스로 재귀 호출
            visit[i] = False    # 원소 사용 해제
            tmp.pop()           # 순열에서 현재 원소 제거

# 백트래킹 함수 호출
recur(0)

# 결과 출력
print(ans)

 

4. 코드 설명

순열 생성

• visit 리스트는 각 원소의 방문 여부를 기록합니다. 예를 들어,  N = 3 ,  A = [1, 2, 3] 이라면, visit = [False, False, False]가 됩니다.
• tmp 리스트는 현재 생성된 순열을 저장합니다.

 

백트래킹 함수

 

순열 생성 과정
• 모든 원소를 사용하여 순열을 만든 경우, 인접한 원소의 차의 절댓값의 합을 계산합니다. 예를 들어, 순열이 [1, 3, 2]라면:
•  |1-3| = 2 
•  |3-2| = 1 
• 따라서 합은  2 + 1 = 3 이 됩니다.
• 이 값을 ans 변수와 비교하여 최대 값을 갱신합니다.

함수 동작 예시
1) 초기 상태
• tmp = [], visit = [False, False, False]
2) 첫 번째 원소 선택
• visit[0] = True, tmp = [1]
• 재귀 호출: recur(1)
3) 두 번째 원소 선택
• visit[1] = True, tmp = [1, 2]
• 재귀 호출: recur(2)
4) 세 번째 원소 선택
• visit[2] = True, tmp = [1, 2, 3]
• 모든 원소 사용, 차의 합 계산
•  |1-2| + |2-3| = 1 + 1 = 2 
• ans 갱신 (현재 2)
5) 백트래킹 진행
• visit[2] = False, tmp = [1, 2]
• visit[1] = False, tmp = [1]
• visit[0] = False, tmp = []
6) 다른 순열 생성 반복
• 새로운 순열 [1, 3, 2], [2, 1, 3], 등등을 생성하여 최댓값을 계산합니다.
• 예를 들어, [1, 3, 2]인 경우:
•  |1-3| + |3-2| = 2 + 1 = 3 
• ans 갱신 (현재 3)

 

5. Github으로 확인

coTest/BOJ/BOJ01_06_03_10819.py at main · pcy4196/coTest