[백준] 순열 (Permutation)

1~N까지로 이루어진 순열, 순서가 중요하다.

다음 순열

순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열을 찾는 방법

https://www.acmicpc.net/problem/10972

더보기

def solution(arr):
    i = len(arr)-1
    while i>0 and arr[i-1] >= arr[i]:
        i -= 1
    if i<=0:
        return -1
    j = len(arr)-1
    while arr[j] <= arr[i-1]:
        j -= 1
    arr[i-1],arr[j] = arr[j],arr[i-1]
    j = len(arr)-1
    while i<j:
        arr[i],arr[j] = arr[j],arr[i]
        i+=1
        j-=1
    return arr


n = int(input())
arr = list(map(int,input().split()))
ans = solution(arr)
for a in ans:
    print(a,end=" ")

이전 순열

걍 반대로 뒤집으면 된다.

https://www.acmicpc.net/problem/10973

더보기

def solution(arr):
    i = len(arr)-1
    while i>0 and arr[i-1] <= arr[i]:
        i -= 1
    if i<=0:
        return -1
    j = len(arr)-1
    while arr[j] >= arr[i-1]:
        j -= 1
    arr[i-1],arr[j] = arr[j],arr[i-1]
    j = len(arr)-1
    while i<j:
        arr[i],arr[j] = arr[j],arr[i]
        i+=1
        j-=1
    return arr


n = int(input())
arr = list(map(int,input().split()))
ans = solution(arr)
if ans==-1:
    print(-1)
else:
    for a in ans:
        print(a,end=" ")

모든 순열

https://www.acmicpc.net/problem/10974

파이썬의 itertools를 이용했다.

더보기

from itertools import permutations

n = int(input())
arr = list(range(1,n+1))
for a in list(permutations(arr,n)):
    for b in a:
        print(b,end=" ")
    print()

차이를 최대로

from itertools import permutations

n = int(input())
arr = list(map(int,input().split(" ")))
arr.sort()

ans = 0
arr = list(permutations(arr,n))
for ar in arr:
    sum = 0
    for idx in range(len(ar)-1):
        sum += abs(ar[idx]-ar[idx+1])
    if ans < sum:
        ans = sum

print(ans)

외판원 순회2

이 문제는 사실 어렵다고 생각했던 문제였는데 원리를 알게되니 풀이할 만했다.

import sys
from itertools import permutations

n = int(input())
arr = []
for _ in range(n):
    arr.append(list(map(int,input().split(" "))))

li = permutations(list(range(n)),n)
ans = sys.maxsize
for l in li:
    if l[0] != 0:
        break
    sum = 0
    ok = True
    for idx in range(len(l)-1):
        if arr[l[idx]][l[idx+1]] == 0:
            ok = False
            break
        sum += arr[l[idx]][l[idx+1]]
    if ok and arr[l[-1]][l[0]] != 0:
        sum += arr[l[-1]][l[0]]
        ans = min(ans,sum)
print(ans)

로또

 

연산자 끼워넣기