Coding 공부

import sys

def input():
    return sys.stdin.readline()

N = int(input())
INF = float('inf')
dp = [INF for _ in range(101)]
dp[2] = 1
dp[3] = 7
dp[4] = 4
dp[5] = 2
dp[6] = 6
dp[7] = 8
dp[8] = 10

for num in range(9,101):
    for i in range(2,8):
        if i != 6:
            dp[num] = min(dp[num],dp[num-i]*10+dp[i])
        else:
            dp[num] = min(dp[num],dp[num-i]*10)
for _ in range(N):
    k = int(input())
    
    max_value = ('7' if k%2 else '1' ) +'1'*(k//2-1)
    print(dp[k],max_value)

이 문제를 푸는 방식은 다음과 같다.

2개부터 8개까지의 성냥개비를 이용해서 만들 수 있는 최소의 수가 있다.

먼저 이 수들을 각각 저장을 해주는 것이다.

단 여기서 주의해야할 점은 성냥개비의 개수가 6개일때다.

6개일때는 원래 최저의 수는 0이지만, 자리수가 1개일때 0이 올수가 없다. 이 점만 주의해주면 된다.

이렇게 2~8개의 최소 숫자를 구해주고

9개부터는 그리디하게 찾아주면 된다.

dp [ 현재 성냥의 개수 - i개 ] *10 + dp[i] 와 dp[현재 성냥의 개수] 의 최소값을 비교해서 갱신해주면 된다.

그리고 위에 말했듯이 6개일때는 가장 작은 수는 0 이므로 *10만 해주면 된다.

이렇게 최소 숫자를 구했으면,

최대 숫자를 구해야한다.

여기서 가장 큰 숫자를 만드는 법은 가장 적은 개수로 만들수 있는 1로 채우는 것이다.

그런데 이럴때 문제는 성냥의 개수가 홀수일때 문제가 된다.

성냥의 개수가 홀 수 일때 1개가 남아서, 어떠한 숫자도 만들수 없다.

그러므로 주어진 성냥개비의 숫자가 홀수이면, 가장 앞의 수를 1이 아닌 성냥개비 3개로 만들수 있는 가장 큰수를 만들어줘야한다.

그에 부합하는 숫자는 7 이므로,

주어진 성냥 개비의 숫자가 홀수이면 7 아니면 1을 붙이고, 성냥개비를 2로 나눈 몫에서 1을 뺀숫자만큼 붙여주면 된다.

def solution(ind,diff):
    if diff > 250000:
        return -INF
    if ind == N:
        if diff == 0:
            return 0
        else:
            return -INF
    if dp[ind][diff] != -1:
        return dp[ind][diff]

    dp[ind][diff] = solution(ind+1,diff+arr[ind])
    dp[ind][diff] = max(dp[ind][diff],solution(ind+1,diff))
    if arr[ind] > diff:
        dp[ind][diff] = max(dp[ind][diff],diff + solution(ind+1,arr[ind]-diff))
    else:
        dp[ind][diff] = max(dp[ind][diff],arr[ind] + solution(ind+1,diff-arr[ind]))
    return dp[ind][diff]

N = int(input())
arr = list(map(int,input().split()))
arr = arr + [0]
INF = float('inf')
dp = [[-1] * 500001 for _ in range(N+1)]

result = solution(0,0)
if result == 0:
    print(-1)
else:
    print(result)

힘들게 풀었던 문제이다.

dp의 테이블에서 행은 현재의 index를 말하며, 열은 두 탑의 격차의 절대값을 말한다.

재귀함수를 통해 짰는데.

첫번째 : 해당 블록을 높이가 더 높은 쪽에 놓았을때,

두번째 : 해당 블록을 놓지 않았을때

세번째 : 높이가 낮은 블록에 놓았을 때 : 이 때 주의해야할 것은 현재 공통적으로 쌓아올려진 높이는 diff와 arr[ind]의 두 크기 중 작은 것에 된다.

이렇게 3가지 경우로 나뉘며, 세번째에는 격차가 클때와 현재 블록이 클때로 나뉘어서 된다.

이렇게 재귀를 하면서 마지막에서 들어온 diff가 0이면 높이가 같은것이므로 0을 반환해주고, 그게 아니면 두 높이가 다른것이므로, -INF를 반환해준다.

이게 내 첫번째 풀이였고, 실행시간은 3900ms로 엄청 느렸다.

그래서 다른 사람 풀이를 보고 공부한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

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

if N == 1:
    print(-1)
else:
    total_sum = sum(arr)
    dp = [[-1] * total_sum for _ in range(N)]
    dp[0][0] = 0
    dp[0][arr[0]] = arr[0]
    for ind in range(N-1):
        for j in range(total_sum//2+1):
            if dp[ind][j] != -1:
                # 다음 거의 블록을 쓰지 않을때
                dp[ind+1][j] = max(dp[ind][j],dp[ind+1][j])
                # 두 탑 중 더 높은 탑쪽에 블록을 쌓을때
                if j + arr[ind+1] < total_sum:
                    dp[ind+1][j+arr[ind+1]] = max(dp[ind+1][j+arr[ind+1]],dp[ind][j]+arr[ind+1])
                # 더 낮은 탑 쪽에 쌓는데 새로 쌓는 블록이 기존 블록보다 높을때 와 아닐때
                if arr[ind+1] > j:
                    dp[ind+1][arr[ind+1]-j] = max(dp[ind+1][arr[ind+1]-j],dp[ind][j] + arr[ind+1]-j)
                else:
                    dp[ind+1][j-arr[ind+1]] = max(dp[ind+1][j-arr[ind+1]],dp[ind][j])
    if dp[-1][0] == 0:
        print(-1)
    else:
        print(dp[-1][0])

위와 dp 테이블은 동일하다. 그런데 전체 input의 합을 구하고, 그거의 반만큼만 반복을 돌리도록 했다.

그래서 위에서는 재귀를 통해서 돌아가다 보니, 무조건 3개의 함수가 실행되다보니 밑의 코드보다 훨씬 오래걸린다.

밑의 코드는 50*250000이 최대 횟수로 볼수 있으므로, 위의 것보다 연산량에 이득을 본것 같다.

여기도 위와 비슷하게,

아무것도 놓지 않았을때

두 탑 중 더 높은 탑쪽에 쌓았을때,

두 탑 중 더 낮은 탑쪽에 쌓았을때,

를 구분해서 놓으면 된다.

그리고 dp에 저장되는 값은 해당 index에서 두 탑의 높이가 diff만큼 차이가 날때, 그때 더 높은탑의 크기를 저장해놓는 것이므로,

그것을 잘 구분해서, dp에 저장시켜주면 된다.