정글사관학교 29일차 TIL: 점프(#2253), 멀티탭 스케쥴링(#1700)

1. 점프(#2253)

 

처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다.

 

풀이에서는 속도를 dp 테이블에서 value가 아니라 행에 저장하는 방식으로 진행했다. (참고했던 풀이는 여기와 여기)

 

dp 테이블을 dp[i][v]로 구성하여 도착지인 i번째 돌에 v의 속도로 도착하는 경우의 수 중 최소 점프 횟수를 value로 저장한다. i번째 돌에 v만큼의 속도로 도착하려면 출발지점은 반드시 i-v번째 돌이어야 한다. 이 돌에서 v의 속도로 갈 수 있는 경우는 총 세 가지이다.

 

1. dp[i-v][v-1]에서 v+1로 가속을 해서 올 때

2. dp[i-v][v]에서 가속 없이 동일한 속도 v로 올 때

3. dp[i-v][v+1]에서 속도를 줄여 v-1로 올 때

 

이전 i-v에서의 경우 세 가지에다가 i-v => v로 뛰는 한 번을 더해주면 dp[i][v]가 되는데, 우리는 이 중 최소로 뛰는 횟수를 세고 싶으니 점화식은 아래와 같다.

 

dp[i][v] = min(dp[i-v][v-1], dp[i-v][v], dp[i-v][v+1]) + 1

 

여기에다가 작은 돌에는 갈 수 없다는 표시를 해주면 된다.

 

dp 테이블의 이차원 배열의 크기는 어떻게 설정할까? 행의 개수는 돌의 개수 N만큼일테고, 한 행의 길이에는 v가 들어가게 될텐데 이때 v의 최댓값이 N에 따라 어떻게 바뀔지를 생각해보면 된다.

 

각 N에 대해서 V가 최대가 될 때만 생각해보자.

 

N = 2일 때, V = 1이다. (1번 돌에서 1칸 뛰어서 2번 돌)

N = 3일 때, V = 2이다. (1-> 2(+1) & 2번 돌에서 (+1) 3번 돌)

N = 4일 때, V = 2이다. (1-> 2(+1) & 2번 돌에서 (+2) 4번 돌)(2번 뛰어서 갈 수 있는 최대: 4)

N = 5일 때, V = 3이다. (1-> 2(+1) & 2번 돌에서 (+2) 4번 돌 & 4번 돌에서 (+1) 5번 돌 )

 

이제 최대로 뛰어서 갈 수 있는 거리만 기록해보면

 

N = 7일 때, V = 3이다. (1-> 2(+1) & 2번 돌에서 (+2) 4번 돌 & 4번 돌에서 (+3) 7번 돌 ) (3번 뛰어서 갈 수 있는 최대: 7)

 

N = 8, 9, 10일 때, V = 4이다. (1번돌 ->1+2+3+1/2/3)(여기는 최대 X)

 

N = 11일 때, V = 4이다. (1-> 2(+1) & 2번 돌에서 (+2) 4번 돌 & 4번 돌에서 (+3) 7번 돌 & 7번 돌에서 (+4) 11번 돌 ) (4번 뛰어서 갈 수 있는 최대: 11)

 

.

.

.

 

이렇게 N과 V의 관계를 살펴보면, 한 번에 뛸 수 있는 최대 거리를 기준으로 N = 1+ (V(V+1)/2)라는 관계식이 형성된다. 이때 V(V+1)/2는 초항이 1이고 공차가 1인 등차수열의 합과도 같다. 즉, 1번 돌에서 출발해 속도가 끊임없이 1씩 증가하며 점프할 때 N에 도달했을 때의 속도의 근사값에 해당한다. 이렇게 주어진 N으로부터 dp에서 행의 길이를 계산할 수 있다. 위의 식 N = 1+ (V(V+1)/2)을 V에 대해서 정리하면 dp 테이블에서 행의 길이를 N에 대해 표현할 수 있게 된다. 정수로 나타나야 하니 아래와 같다.

 

V * (V + 1) / 2 = N
V ** 2 + V = 2N 
V = (2N - V) ** 0.5 < 2N ** 0.5

이제 전체 코드를 보자. 아래 int(sqrt(2*N))+2) 이 부분을 위에서 설명한 것으로 이해하면 나머지는 위의 점화식을 기반으로 쉽게 이해할 수 있다.

from sys import stdin
from math import sqrt
input = stdin.readline

def solve():
    N, M = map(int, input().split())
    dp = [[float('inf')] * (int(sqrt(2*N))+2) for _ in range(N+1)]
    dp[1][0] = 0
    trap = set()
    for _ in range(M):
        trap.add(int(input()))
    
    for i in range(2, N+1):
        if i in trap:
            continue
        for v in range(1, int(sqrt(2*i)) + 1): # v 범위를 제한 => 들어오는 i에 대해서만
            dp[i][v] = min(dp[i-v][v-1], dp[i-v][v], dp[i-v][v+1]) + 1
    
    result = min(dp[N])
    if result == float('inf'):
        print(-1)
    else:
        print(result)

solve()

 

 

2. 멀티탭 스케쥴링(#1700)

내가 문제에 접근했던 방식은 이후에 설명할 풀이와 비슷하긴 했다. (물론 가장 마지막 케이스는 1도 떠올리지 못함..)멀티탭을 N개 길이의 리스트로 만드는 것까지도 좋았는데 여기에 기존에 받아왔던 리스트에서 각 원소의 개수를 카운트한 개수를 저장하는 리스트를 따로 만들면서 엄청 복잡해지기 시작했다. 그냥 주어진 리스트를 그대로 쓰면 간결하게 풀 수 있었는데 여기서부터 꼬이기 시작.. 코드 라인도 55줄이나 나오더라. 반면, 아래 소개할 풀이는 대략 20여 줄이면 끝난다.

 

풀이 논리는 비슷하다. 구현 능력이 아직 많이 부족하다는 걸 느꼈던 부분. (연습만이 살 길이다!)

 

1. 주어진 가전기기 리스트에서 순서를 지키며 왼쪽부터 하나씩 읽어온다. (for i in li)
2. i가 이미 멀티탭에 끼워져 있다면 => 패스한다. (if i in multap: pass)
3. 멀티탭에 i가 없는데 멀티탭에 빈 칸이 있다면 (elif 0 in multap) 해당 인덱스를 반환시켜서 그 자리에 i를 넣는다.
4. (여기가 중요)i가 멀티탭에 끼워져 있지 않은데 멀티탭에 빈 칸도 없는 상황일 경우

4번에서 잠깐 끊어서 간다. 처음에 풀 때 이 부분을 놓쳐서 반례를 열심히 찾아 헤멨다. 처음에는 남아있는 가전 기기 리스트에서 콘센트에 끼워야 할 횟수가 가장 적은 애를 뽑는 식으로 코드를 짰는데 계속 틀렸다고 나오더라. 그런데 이게 아니었다. 대표적인 반례는 아래와 같은 케이스이다.

 

Input:
2 15
3 2 1 2 1 2 1 2 1 3 3 3 3 3 3

Ans: 2
Wrong: 7

아직 아무 것도 코드에 꽂지 않은 시점에서 각 가전 기기를 꽂는 횟수는 아래와 같다.

1: 4회

2: 4회

3: 7회

 

첫번째부터 시작해 3과 2를 꽂은 시점에서 1을 새로 꽂아야 하는데, 3을 꽂는 횟수가 가장 많이 남았으니(3-2-1을 꽂을 시점에서 3:6회/2: 3회) 3을 내버려두고 2를 빼면 대참사가 발생한다. 1과 2를 계속 반복해서 꽂고 빼고 하니 횟수가 계속 올라가게 된다. 따라서 우리는 1을 꽂는 시점에서, 중복을 제외하고 가장 마지막에 뽑는 애를 앞에서 뽑아야 한다. 즉, 2가 아닌 3을 뽑아야 한다는 뜻이다. (다른 풀이들 읽어보면 알겠지만 그냥 떠올리기 힘든 것 맞으니까 좌절하지 말 것!)

 

최종 코드는 아래와 같다.

 

from sys import stdin
input = stdin.readline

N, K = map(int, input().split())

multap = [0] * N
li = list(map(int, input().split()))
res = swap = num = max_I = 0

for i in li:
    # 이미 i가 멀티탭에 끼워져 있다면
    if i in multap:
        pass
    # 멀티탭에 빈 칸이 있다면 0인 곳에 배정
    elif 0 in multap:
        multap[multap.index(0)] = i
    # i가 멀티탭에 안 끼워져 있고 빈 칸도 없는 상황
    else:
        for j in multap: # 멀티탭을 쭉 스캔
            if j not in li[num:]: # num부터 쭉 스캔 => 처음에는 num == 0 => for 문 한바꾸 돌 떄마다 스캔 위치를 위로 올려
                swap = j
                break
            elif li[num:].index(j) > max_I:
                max_I = li[num:].index(j)
                swap = j
        multap[multap.index(swap)] = i
        max_I = swap = 0
        res += 1
    num += 1
print(res)