[알고리즘] BOJ 10819번 - 차이를 최대로(python3)

* 알고리즘 너무 약해서 기초 문제 50개 목표로 푸는 중...

* 3시간 안에 답을 내지 못하면 답지를 보고 30분 내로 정답 판정을 받고, 3일 뒤 다시 풀어보기

---

Greedy

5 / 50

 

탐색

7 / 50(NEW!)

 

기초 동적 프로그래밍

6 / 50

---

투포인터

1 / 10

 

이분탐색

0 / 10

---

문제

10819번: 차이를 최대로 (acmicpc.net)

10819번: 차이를 최대로

→ solved.ac 기준 실버 2

---

문제 해결 아이디어

최댓값을 구하는데, N이 최대 8이어서 시간 초과 우려 x

→ 브루트포스로, 배열에 들어있는 정수의 순서를 바꾼 모든 경우의 수를 넣어보고, 최댓값을 찾기

→ itertools의 permutations 라이브러리를 사용해서 가능한 순열들을 생성하고, 모두 넣어본 후 반환

---

구현

내 풀이(라이브러리 사용)

import sys
# 배열의 모든 경우의 수를 구하기 위해 라이브러리 사용
from itertools import permutations

input = sys.stdin.readline

def expr(array):
  result = 0
  for i in range(n - 1):
    result += abs(array[i] - array[i + 1])
  return result
  
n = int(input())
array = list(map(int, input().split()))

answer = 0
for case in permutations(array):
  answer = max(answer, expr(case))
  
print(answer)

 

다른 사람 풀이

백트래킹

import sys
input = sys.stdin.readline

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

n = int(input())
graph = list(map(int, input().split())
array = []
visited = [False] * n

answer = INF

def dfs(depth):
	# array의 총 길이가 n일 때 == depth가 n일 때
	if depth == n:
    	result = 0
        for i in range(n - 1):
        	result += abs(graph[array[i]] - graph[array[i + 1]])
        answer = max(result, answer)
        return
    
    # 그 외에는 array에 추가
    for i in range(n):
    	if not visited[i]:
        	visited[i] = True
            array.append(i)
            dfs(depth + 1)
            visited[i] = False
            array.pop()

dfs(0)
print(answer)

 

---

메모

• 걸린 시간: 12분
• itertools 라이브러리를 사용하지 않고 permutation 함수 구현하는 방법

def my_permutation(arr):
    result = [arr[:]]
    c = [0] * len(arr)
    i = 0
    while i < len(arr):
        if c[i] < i:
            if i % 2 == 0:
                arr[0], arr[i] = arr[i], arr[0]
            else:
                arr[c[i]], arr[i] = arr[i], arr[c[i]]
            result.append(arr[:])
            c[i] += 1
            i = 0
        else:
            c[i] = 0
            i += 1
    return result

출처: 파이썬을 파이썬답게 - 순열과 조합 - combinations, permutations | 프로그래머스 스쿨 (programmers.co.kr)

---