[백준] 28286 재채점을 기다리는 중 (python 파이썬)

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

28286번: 재채점을 기다리는 중

---

처음 문제를 읽었을 때는 시간을 어떻게 줄일까 고민했는데, 입력값이 매우 작다.(max(N) = 20, max(K) = 3)

무난한 문제. 백트래킹을 사용해서 최대 개수를 찾아준다.

---

아이디어

1. pull: 번호들을 왼쪽으로 당기는 기능. rotate를 써서 구현했다. for문으로 구현해도 된다.

2. push: 번호를 오른쪽으로 미는 기능. pull과 마찬가지로 rotate를 써서 구현했다.

3. backTracking: K는 작업의 최대 횟수 이므로 K번보다 적게 하는 경우도 고려해줘야 한다. 여러 가지 case 중 최댓값이 나온 걸 return 해준다.

---

전체 코드

from collections import deque

n = 0
result = 0

N, K = map(int, input().split())
answer = list(map(int, input().split()))
OMR = list(map(int, input().split()))

def pull(arr, p):
    a1, a2 = arr[:p], deque(arr[p:])
    a2.rotate(-1)
    a2[-1] = -1
    return a1 + list(a2)

def push(arr, p):
    a1, a2 = arr[:p], deque(arr[p:])
    a2.rotate(1)
    a2[0] = -1
    return a1 + list(a2)

def dfs(n, Arr):
    global result
    count = 0

    for i in range(N):
        if answer[i] == Arr[i]:
            count += 1

    if count > result:
        result = count

    if n < K:
        for i in range(N):
            dfs(n + 1, pull(Arr, i))
            dfs(n + 1, push(Arr, i))

dfs(0, OMR)
print(result)

---

코드 설명

def pull(arr, p):
    a1, a2 = arr[:p], deque(arr[p:])
    a2.rotate(-1)
    a2[-1] = -1
    return a1 + list(a2)

pull과 push는 다양한 방법으로 구현할 수 있지만, 난 split과 rotate를 써서 구현했다. rotate 메서드를 쓰기 위해 deque를 import 해주자.

 

def backTracking(n, Arr):
    global result
    count = 0

    for i in range(N):
        if answer[i] == Arr[i]:
            count += 1

    if count > result:
        result = count

    if n < K:
        for i in range(N):
            backTracking(n + 1, pull(Arr, i))
            backTracking(n + 1, push(Arr, i))

K값을 제한으로 두고 재귀 함수를 사용해 최대 정답 개수를 찾아준다.