그냥 코딩하는 사람의 블로그

문제 설명

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이 과정

1. 초기 위치를 left는 0, right는 N-1로 둔다.
   • 가장 산성인 용액과, 가장 알칼리성 용액을 가리키도록 함.
2. 만약 현재 left, right가 가리키는 용액의 혼합 특성값이 0보다 크다면
   • right를 1 줄여줌. (알칼리성 용액의 농도를 낮추어야 0에 가까워진다.)
3. 만약 현재 left, right가 가리키는 용액의 혼합 특성값이 0보다 작다면
   • left를 1 늘려줌. (산성 용액의 농도를 낮추어야 0에 가까워진다.)
4. 과정을 진행하면서, 특성값의 합이 가장 낮을 때의 두 용액의 특성값을 저장해 둔다.

소스 코드

N = int(input())
ph = list(map(int, input().split()))

left = 0
right = N-1

min_ph = int(10e9)
value1, value2 = 0, 0

while left < right:
    if abs(ph[left] + ph[right]) <= min_ph:
        min_ph = abs(ph[left] + ph[right])
        value1 = ph[left]
        value2 = ph[right]

    if ph[left] + ph[right] > 0:
        right -= 1
    else:
        left += 1

print(value1, value2)

풀이 과정

• 이전 챌린지에서 다른 사람들의 풀이를 보니, 컴프리헨션과 리스트의 함수들을 사용하는 모습을 보고, 소스가 훨씬 깔끔해 보이고 좋아보여서 최대한 사용해 보려고 해봄.

1. 최종적으로 목표는 리스트에 [승률, 몸무게가 무거운 복서를 이긴 횟수, 몸무게, 번호] 요소를 삽입하는것이 목적임.
   • 정렬은 마지막에 리스트의 sort 함수를 사용할 예정
2. 따라서, 각 인원에 대해서 조사
   • 인원의 승률을 구할 때는, 한번도 붙어보지 않은 경우에는 0, 한번이라도 붙어본 경우에는 W의 개수 / (W의 개수 + L의 개수)
   • 몸무게가 무거운 복서를 이긴 횟수를 구할 때는, 상대가 나보다 무거우면서 head2head의 값이 W인 개수를 구하면 된다.
   • 마지막에 현재 인원의 몸무게와 번호를 뒤에 붙여서 최종 리스트에 넣어주면 된다.
3. 최종 리스트 정렬
   • 정렬을 할 때, 승률로는 내림차순, 무거운 복서 이긴 횟수로 내림차순, 몸무게로 내림차순, 번호로 오름차순 순으로 정렬한다.
   • 파이썬에서 오름차순의 경우는 그냥 써주면 되지만, 내림차순의 경우는 약간의 꼼수로 -를 붙여주면 된다.
4. 번호만 따로 뽑아서 answer에 저장한 후 리턴해주면 된다.

소스 코드

def solution(weights, head2head):
    # [승률, 몸무게가 무거운 복서를 이긴 횟수, 몸무게, 번호]
    answer = []
    people_count = len(weights)
    result = []
    for i in range(people_count):
        if head2head[i].count('N') == len(head2head[i]): 
            winrate = 0
        else: 
            winrate = head2head[i].count('W') / (head2head[i].count('W') + head2head[i].count('L')) 
        heavy_win_count = len([1 for j in range(people_count) if weights[i] < weights[j] and head2head[i][j] == 'W'])
        result.append([winrate, heavy_win_count, weights[i], i+1])

    result.sort(key=lambda x:(-x[0], -x[1], -x[2], x[3]))

    for _, __, ___, n in result:
        answer.append(n)

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

풀이 과정

1. 사전순으로 정렬된 리스트를 얻어야 하므로, Recursion으로 구현 할 때 현재 합에서 1->2->3 순으로 더하도록 Recursion을 진행한다.
2. Recursion을 진행한다.
   • 현재 사용한 숫자들에 1, 2, 3을 넣고, 사용한 숫자를 합계에 더해서 다음 Recursion 호출
   • Recursion을 진행하다 현재 합계가 n보다 커진다면 종료
   • n과 같다면 리스트에 추가하고 종료한다.
3. 2번 과정을 진행하면 결국 1,2,3의 합으로 나타내는 모든 방법이 정렬되어 있는 리스트를 얻게 된다.
   • 따라서, k-1번째 인덱스의 방법을 출력해주면 된다.
   • 이 때, k-1이 방법의 수보다 큰 경우가 있으므로, 이 때는 -1을 출력해준다.

소스 코드

n, k = map(int, input().split())

case = []
def dfs(numbers, sumation, target):
    global case

    if sumation == target:
        case.append(numbers)
        return
    if sumation > target:
        return

    for i in [1, 2, 3]:
        dfs(numbers + [i], sumation + i, target)

dfs([], 0, n)
if k - 1 < len(case):
    print("+".join(map(str, case[k-1])))
else:
    print(-1)

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

풀이 과정

• 이렇게 2+1+1이랑 1+1+2, 1+2+1을 모두 같은 것으로 처리하기 위해서는 한 점(dp[i])에서 dp[i]-1, dp[i]-2, dp[i]-3일때를 한번에 더해서는 겹치는 수가 생겨서 안된다.

• 정수 1,2,3을 기준으로, 맨 마지막에 1이 나왔을 때를 계산하고, 맨 마지막에 2가 나왔을 때를 계산하고, 3이 나왔을 때를 계산해주는 방식으로 테이블을 채운다.

• 따라서,

  • 1일때는 dp[i] = dp[i] + dp[i-1],
  • 2일때는 dp[i] = dp[i] + dp[i-2],
  • 3일때는 dp[i] = dp[i] + dp[i-3]

소스 코드

total = int(input())
for _ in range(total):
    T = int(input())
    dp = [1] + [0] * T
    for i in [1, 2, 3]:
        for j in range(1, T+1):
            if j - i >= 0:
                dp[j] += dp[j-i]
    print(dp[T])

게시판에 어떠한 기능을 추가해볼까 고민하던 중, 글을 쓸 때 글의 작성부분이 밋밋한 점이 마음에 들지 않았다. 직접 구현하기에는 너무 어려울것 같아 구글링을 해보니, Summernote라는 에디터를 사용하면 된다고 하더라. 사용법을 찾아보니 쉬운것 같아 공유해보고자 한다.

출처 : https://summernote.org/getting-started/#include-jscss

1. HTML 헤더

• Bootstrap으로 구현된 에디터이다 보니, HTML 헤더가 필요하다.

    <!DOCTYPE html>
    <html lang="en">
    ...
    </html>

2. 필요한 파일 추가

<!-- include libraries(jQuery, bootstrap) -->
<link href="https://stackpath.bootstrapcdn.com/bootstrap/3.4.1/css/bootstrap.min.css" rel="stylesheet">
<script src="https://code.jquery.com/jquery-3.5.1.min.js"></script>
<script src="https://stackpath.bootstrapcdn.com/bootstrap/3.4.1/js/bootstrap.min.js"></script>

<!-- include summernote css/js -->
<link href="https://cdn.jsdelivr.net/npm/summernote@0.8.18/dist/summernote.min.css" rel="stylesheet">
<script src="https://cdn.jsdelivr.net/npm/summernote@0.8.18/dist/summernote.min.js"></script>    

3. 에디터 불러오기

• 에디터를 적용할 textarea 만들기

    <textarea class="form-control" name="content" id="content" rows="10">{{ form.content.value|default_if_none:'' }}</textarea>

• 해당 textarea에 summernote 적용

    <script type="text/javascript"> 
      $(document).ready(function() { $("#content").summernote(); }) 
    </script>

4. Django에서 불러오는 부분 처리

• Django에서 HTML 텍스트를 그대로 불러올 수 없음.
• 템플릿 필터중에 safe 필터를 사용
  • 보안상에 문제가 있을수도 있으니 신중히 사용해야 함.
  • 악성 스크립트 삽입 공격에 대한 고려가 필요함.
    • 다행히도 Summernote 에디터에서는 입력한 데이터에 대해서는 이스케이프가 적용되서 HTML 태그를 생성하므로 safe 필터를 사용해도 문제가 없을 것이라고 생각된다.
  • 이스케이프가 적용되지 않음, 기본적으로는 이스케이프 적용 => HTML 태그를 적용.

<div class="card-text" style="white-space: pre-line;">
  {{ question.content|safe}}
</div>

이스케이프 적용 / 미적용 차이점

• 이스케이프가 적용되지 않음

    <b>

• 이스케이프가 적용됨

    <b>

문제 설명

문제

심마니 영재는 산삼을 찾아다닌다.

산삼을 찾던 영재는N개의 돌이 일렬로 나열되어 있는 강가를 발견했고, 마지막 돌 틈 사이에 산삼이 있다는 사실을 알게 되었다.

마지막 돌 틈 사이에 있는 산삼을 캐기 위해 영재는 돌과 돌 사이를 점프하면서 이동하며 점프의 종류는 3가지가 있다.

점프의 종류에는 현재 위치에서 다음 돌로 이동하는 작은 점프, 1개의 돌을 건너뛰어 이동하는 큰 점프, 2개의 돌을 건너뛰어 이동하는 매우 큰 점프가 있다.

각 점프를 할 때는 에너지를 소비하는데, 이 때 작은 점프와 큰 점프시 소비되는 에너지는 점프를 하는 돌의 번호마다 다르다.

매우 큰 점프는 단 한 번의 기회가 주어지는데, 이때는 점프를 하는 돌의 번호와 상관없이 k만큼의 에너지를 소비한다.

에너지를 최대한 아껴야 하는 영재가 산삼을 얻기 위해 필요한 에너지의 최솟값을 구하여라.

영재는 첫 번째 돌에서부터 출발한다.

입력

첫 번째 줄에는 돌의 개수N이 주어진다.

N - 1개의 줄에 걸쳐서, 1번 돌부터 N - 1번 돌 까지의 작은 점프를 하기 위해 필요한 에너지, 큰 점프를 하기 위해 필요한 에너지가 주어진다.

마지막 줄에는K가 주어진다.

출력

산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다.

제한

• 1 ≤ N ≤ 20
• 작은 점프, 큰 점프 시 필요한 에너지와 K는 5,000을 넘지않는 자연수이다.

풀이 과정

• 2차원 DP 테이블을 구성한다.

  • DP[i][0] : i번째 돌까지의 최소비용, 매우 큰 점프 사용하지 않음.
  • DP[i][1] : i번째 돌까지의 최소비용, 매우 큰 점프 사용

• 현재 위치가 x라고 둘 때, 갈수있는 모든 돌의 비용들을 갱신한다.

  • 점프(+1)하는 경우, 큰점프(+2) 하는 경우, 매우 큰 점프(+3) 하는 경우
  • 매우 큰 점프의 경우, DP[x][1]일때는 이미 점프한 경우이므로 점프할수 없으므로, DP[x][0]에 대해서만 고려한다.

• 마지막으로, DP[N]의 최솟값을 출력해주면 된다.

  • 매우 큰점프를 사용하였거나, 사용하지 않았을 때중 최솟값

소스 코드

import sys
from collections import deque

N = int(input().rstrip())

small = [0] * (N+1)
big = [0] * (N+1)

for i in range(1, N):
    a, b = map(int, input().rstrip().split())
    small[i], big[i] = a, b

K = int(input().rstrip())

INT_MAX = int(10e9)
dp = [[INT_MAX] * 2 for _ in range(N+1)]
dp[1][0], dp[1][1] = 0, INT_MAX
for i in range(1, N):
    dp[i+1][0] = min(dp[i+1][0], dp[i][0]+small[i])
    dp[i+1][1] = min(dp[i+1][1], dp[i][1]+small[i])
    if i + 2 <= N:
        dp[i+2][0] = min(dp[i+2][0], dp[i][0]+big[i])
        dp[i+2][1] = min(dp[i+2][1], dp[i][1]+big[i])
    if i + 3 <= N:
        dp[i+3][1] = min(dp[i+3][1], dp[i][0] + K)


print(min(dp[N]))

문제 설명

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

풀이 과정

1. [1~9]까지의 값을 미리 큐에 넣어둔 다음 BFS를 진행한다.
   • N = 0일때는 따로 예외로 처리해주어야 함.
   • 현재 값을 N이라고 할 때, N의 맨 마지막 자리 숫자보다 작은 숫자들을 뒤에 붙여서 큐에 다시 넣어준다.
   • 예시로 N이 2라고 할때, 20, 21을 큐에 넣어준다.
2. BFS를 진행하면서 큐가 비게 되면 N번째 감소하는 수는 만들 수 없는 것이므로 -1 리턴
   • 큐에서 뺀 수가 N번째 숫자면 해당 수 리턴

소스 코드

import sys
from collections import deque

N = int(input().rstrip())

def bfs(N):
    queue = deque([i for i in range(1, 10)])
    count = 0

    while queue:
        t1 = queue.popleft()
        count += 1
        if count == N:
            return t1
        dest = int(str(t1)[-1])
        for i in range(dest):
            queue.append(int(str(t1) + str(i)))

    return -1

if N == 0:
    print(0)
else:
    print(bfs(N))

문제 설명

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 [i][j]형태로 주어진다. [i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, [i][j] 는 [j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. [i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 [i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

풀이 과정

• DFS로 풀수도 있을거라고 생각하지만, 도시의 개수가 최대 10개로 매우 작으므로 전체 경우의 수를 조합으로 구해서 해결

1. 각 도시들을 번호를 붙임
   • N개의 도시라고 하면, [0, 1, 2, ... , n-1]까지 번호 붙임
   • [i][j]를 i에서 j도시로 이동할 때 비용이라고 둔다.
2. 번호들로 조합을 구성한다.
   • itertools.permutations 사용
   • 이후, 시작도시로 돌아와야 하므로 각각의 케이스의 맨 뒤에 맨 첫번째 도시 번호를 붙여준다.
3. 각각의 케이스에 대해 비용이 얼마나 나오는지 계산
   • 진행하다가 [i][j]가 0이 되는 경우는 길이 없는것이므로 중지
4. 비용의 최솟값을 출력해준다.

소스 코드

import sys
from itertools import permutations

input = sys.stdin.readline
N = int(input().rstrip())
W = [list(map(int, input().rstrip().split())) for _ in range(N)]

total_case = list(permutations([i for i in range(N)], N))

def check_case(W, case):
    case = case + (case[0], )
    cost = 0
    for i in range(1, len(case)):
        if W[case[i]][case[i-1]] == 0:
            return int(10e9)
        cost += W[case[i]][case[i-1]]

    return cost

answer = int(10e9)
for case in total_case:
    answer = min(answer, check_case(W, case))

print(answer)

문제 설명

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력 한다.

풀이 과정

• 이전에 푼 문제중에 다음 순열이라는 문제가 있는데, 해당 문제와 거의 유사하나 몇몇 부분을 바꾸어주어야 하는 부분이 있음.

1. 순열을 오른쪽에서 왼쪽으로 진행하면서 array[i-1]>array[i]인 구간을 찾는다.
   • 이 때, 이러한 구간이 없으면 제일 첫번째 순열인 것이므로 -1을 출력해주면 된다.
   • 구간이 있다면, i-1이 바뀌게 될 요소의 인덱스이다.
2. 다음으로, array[i-1]보다 작은 요소의 인덱스를 오른쪽에서 왼쪽으로 진행하면서 찾는다.
   • 이 요소의 위치를 j라고 두자.
3. array[i-1], array[j]를 서로 바꾸어 준다.
4. 이후, i 이후의 배열들을 뒤집어준다.
   • 내림차순으로 정렬해야 하는데, (1)에서 i를 찾을때, i 이후는 모두 오름차순임을 알 수 있다.
   • 따라서 뒤집어 주면 i 이후는 모두 내림차순이 된다.
5. 배열을 출력해주면 끝

소스 코드

import sys

n = int(sys.stdin.readline().rstrip())

sequence = list(map(int, sys.stdin.readline().rstrip().split()))

def prev_permutation(sequence):
    i = len(sequence) - 1

    # sequence[i-1] > sequence[i]인 부분을 찾음 => i-1이 바꿔지게 될 위치임.
    while i > 0 and sequence[i-1] < sequence[i]:
        i = i - 1

    if i == 0:
        return None

    swap_pos = i-1
    j = len(sequence) - 1
    # 오른쪽에서 시작했을 때, 바꿔지게 될 요소보다 작은 수들중 처음 나오는 요소가
    # 바뀌어지게 된다.
    while j > 0 and sequence[swap_pos] <= sequence[j]:
        j = j - 1

    sequence[swap_pos], sequence[j] = sequence[j], sequence[swap_pos]

    # 바뀌는 점 이후는 내림차순이 되어야 함
    # 위 while문을 보면 알겠지만.. 바뀌는 위치 기준으로 오른쪽은 오름차순이 되어 있음.
    # 따라서, 그냥 뒤집어주면 된다.
    sequence = sequence[:i] + sequence[i:][::-1] 
    return sequence


p = prev_permutation(sequence)
if p == None:
    print(-1)
else:
    print(*p)

문제 설명

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

풀이 과정

1. 처음에 생각했을 때는, 최댓값, 최솟값, 두번째 최댓값, ... 이런식으로 배열해야 되는줄 알았으나.. 그냥 틀리길래 입력의 크기를 보니 최대 8개이므로 전수조사 하면 된다.
2. 파이썬에서 제공하는 itertools.permutations 함수 사용
   • permutations(list, 갯수) => list에서 갯수만큼 뽑아서 조합
3. 각각의 조합들에 대해 식의 값을 구한 후, 최댓값을 출력해주면 된다.

소스 코드

import sys
from itertools import permutations

input = sys.stdin.readline
N = int(input().rstrip())
array = list(map(int, input().rstrip().split()))
length = len(array)

total_case = list(permutations(array, length))

def simulation(case):
    value = 0
    for i in range(1, len(case)):
        value += abs(case[i] - case[i-1])

    return value

answer = 0
for case in total_case:
    answer = max(answer, simulation(case))

print(answer)