100년 뒤 개발자 한승규입니다.

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

실버 2이지만 생각보다 오래걸렸다.

이 방법으로 푸는 게 아닌거라고는 알고 있지만, 어떻게든 풀어는 보았다.

DP인 만큼 일단 기억할 배열을 만든다.

result = [[None] for i in range(N)]

그리고 2중 반복문으로 해당 수로 만든 수열과 DP에 기억된 수열 중 최대 값이 본인보다 작은 수열 중에서 길이가 더 긴 수열로 본인 차례의 가장 긴 수열을 만들고, 마지막 결과에서 그 수열 중에서 길이가 가장 긴 수열의 길이를 출력하는 것이다.

import sys

N = int(input())

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

result = [[None] for i in range(N)]

for i in range(N):
    cur_list = [A[i]]
    for t in range(i):
        if A[i] > A[t]:
            if len(cur_list) < len(result[t]) + 1:
                cur_list = result[t] + [A[i]]
    result[i] = cur_list

result.sort(key= lambda x : len(x))

print(len(result[-1]))

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

DP에서 중요하다고 생각되는 내용 중 하나인 배낭 문제이다.

import sys

N, K = map(int, sys.stdin.readline().split())
dp = [[0] * (K + 1) for i in range(N + 1)]
thing = [[0, 0]]

for i in range(N):
    thing.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N + 1):
    w = thing[i][0]
    v = thing[i][1]
    for t in range(1, K + 1):
        if t < w:
            dp[i][t] = max(dp[i-1][t], dp[i][t-1])
        else:
            dp[i][t] = max(dp[i-1][t], dp[i][t-1],dp[i-1][t-w] + v)



print(dp[-1][-1])

옛날에 풀었던 코드이다.

너무 오래 전이라 기억도 안나고, 이번 주 과제이기 때문에 다시 풀어보도록 했다.

우선 DP 답게 기억할 배열이 필요하다.

범위는 무게인 0부터 W까지이다.

이제는 후보들을 반복문으로 돌면서 넣을지 말지를 판단해야 한다.

해당 짐이 들어갈 수 있는 모든 구간에 대해서, 현재 넣을 후보와 이 짐을 넣었을 때의 가치를 비교하고 무엇을 넣을지를 결정하면 된다.

import sys

N, K = map(int, sys.stdin.readline().split())

candidate_weight = []
candidate_value = []

for i in range(N):
    W, V = map(int, sys.stdin.readline().split())
    candidate_weight.append(W)
    candidate_value.append(V)

result = [0 for i in range(K + 1)]

for i in range(N):
    for t in range(candidate_weight[i], K + 1):
        result[t] = max(result[t], result[t-candidate_weight[i]] + candidate_value[i])

print(result[-1])

그래서 당연히 아무 생각없이 이렇게 코드를 만들었었다.

당연히 에러가 발생한다.

만약 가능한 무게가 8이고 4인 짐을 넣으려고 하면

[0, 0, 0, 0, 4, 0, 0, 0, 8] 이렇게 하나의 짐이 2번 들어가기 때문에 안쪽에 있는 반복문은 증가하는 방향이 아니라 감소하는 방향으로 만들어주어야 한다.

import sys

N, K = map(int, sys.stdin.readline().split())

candidate_weight = []
candidate_value = []

for i in range(N):
    W, V = map(int, sys.stdin.readline().split())
    candidate_weight.append(W)
    candidate_value.append(V)

result = [0 for i in range(K + 1)]

for i in range(N):
    for t in range(K, candidate_weight[i] - 1, -1):
        result[t] = max(result[t], result[t-candidate_weight[i]] + candidate_value[i])

print(max(result))

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

DP 문제가 DP로 풀어야 한다는 것을 알고 시작하면, 별로 어려운 거 같지는 않다.

하지만 보통 시간에 막히고 그 때서야 깨닫게되어서 문제이지만...

간단하게 보면 타일은 세로로 1칸 차지하거나, 가로로 2개를 사용해서 2칸 차지하는 2가지 방법 밖에 없다.

결국 n-2일 때의 타일에 가로로 2칸 차지해서 만드는 경우와 n-1일 때 세로로 1칸 차지해서 만드는 경우를 더해주면 된다.

import sys

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

square = [1 for i in range(n + 1)]

for i in range(2, n + 1):
    square[i] = square[i-1] + square[i-2]

print(square[-1] % 10007)

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

일단 동적프로그래밍이다.

조건으로 N이 90까지 주어지는 데, 이거를 직접 10 ** N 이렇게 구하는 건 말도 안된다는 것은 바로 알 수 있었다.

그러고는 예시를 먼저 보자.

1로 끝나는 수 뒤에는 1이 오지 못하고 0만 올 수 있다.

하지만 0으로 끝나는 수 뒤에는 1과 0이 다 올 수 있다.

그러면 N+1에서 1로 끝나는 수의 숫자는 N에서 0으로 끝나는 수의 숫자 일 것이고, 0으로 끝나는 수의 숫자는 N에서 0으로 끝나는 수와 1로 끝나는 수의 합 일 것이다.

이 생각을 바탕으로 N=1일 때의 값은 넣어주고, 입력값 N의 답을 얻을 수 있도록 하였다.

import sys

N = int(sys.stdin.readline())

end_zero = 0
end_one = 1

for i in range(N-1):
    end_zero, end_one = end_zero + end_one, end_zero

print(end_zero + end_one)

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

옛날에 풀었던 문제이지만, 동적 프로그래밍을 복습하는 과정에서 가장 기초적인 문제라 다시 한 번 풀어보았다.

문제를 풀고 나서 옛날에 풀었던 것을 확인 해보았는 데...

N = int(input())

for i in range(int(N/5)+1,0,-1):
    if (N-5*i)%3==0 and N-5*i>=0:
        print(int(i+(N-5*i)/3))
        exit()
if(N%3==0):
    print(int(N/3))
    exit()
else:
    print(-1)

어떻게 풀었는 지는 모르겠지만, 동적프로그래밍이 아니라 그냥 계산으로 푼 것 같다...

동적 프로그래밍답게 지난 계산을 기억할 배열을 만들고 해당 데이터가 존재한다면 그 데이터를 이용해서 현재 데이터를 만들 수 있게 했다.

import sys

N = int(sys.stdin.readline())

sugar = [-1 for i in range(N + 3)]

sugar[3] = 1
sugar[4] = -1
sugar[5] = 1

for i in range(6, N+1):
    if sugar[i-3] == -1 and sugar[i-5] == -1:
        sugar[i] = -1

    elif sugar[i-3] == -1:
        sugar[i] = sugar[i-5] + 1

    elif sugar[i-5] == -1:
        sugar[i] = sugar[i-3] + 1

    else:
        sugar[i] = min(sugar[i-3], sugar[i-5]) + 1

print(sugar[N])

3, 4, 5에 대한 값을 미리 넣어줘야 하는 데 배열을 N+1로 만들어버리면 index 에러가 발생해서

그냥 N+3만큼 미리 만들어버리고 시작했다.

그리고 후에는 반복문을 돌며 3번 전, 5번 전의 계산에서 유효한 값이 있다면 그 중 작은 값에서 +1을 한다

만약 둘 중 하나만 유효한 값이라면 그 값의 +1을 하고, 둘 다 유효하지 않다면 만들 수 없는 경우이기 때문에 -1로 만들어준다.

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

아무 생각 없이 풀어서 한 번 틀렸다.

우선 입력받은 배열을 바로 정렬하고, 그 배열로 부분집합을 만드는 것까지는 바로 생각이 난다.

하지만 그렇게 만든 부분집합에서 조건으로 걸러야 한다.

make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)

이렇게 재귀함수로 현재의 값을 추가하는 집합 하나, 추가하지 않는 집합 하나를 만들어준다.

def make_key(cur_candidate, index):

    if index == C:
        value = len(set(cur_candidate).intersection(important))
        if len(cur_candidate) == L and value >= 1 and (L - value) >= 2:
            for i in cur_candidate:
                print(i, end='')
            print()
            return

    else:
        make_key(cur_candidate + [candidate[index]], index + 1)
        make_key(cur_candidate, index + 1)

이렇게 하나씩 추가하다가 인덱스가 C를 넘어갔을 때, 현재 부분집합의 길이가 L이고 모음이 하나 이상 있고 자음이 2개 이상 있을 때만 출력이 되도록 해줬다.

import sys

L, C = map(int, sys.stdin.readline().split())

candidate = sorted(list(map(str, sys.stdin.readline().split())))

important = {'a', 'e', 'i', 'o', 'u'}


def make_key(cur_candidate, index):

    if index == C:
        value = len(set(cur_candidate).intersection(important))
        if len(cur_candidate) == L and value >= 1 and (L - value) >= 2:
            for i in cur_candidate:
                print(i, end='')
            print()
            return

    else:
        make_key(cur_candidate + [candidate[index]], index + 1)
        make_key(cur_candidate, index + 1)


make_key([], 0)

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

브루트포스 문제들을 모아서 풀다가 풀어보니 크게 어렵지 않게 풀 수 있었다.

간단하게 해당 일정을 추가하는 것과 안추가 하는 것들을 비교해보면 된다.

물론 이 방법도 경우의 수가 엄청 많이 나올 것이다.

def consult(today, cur):
    if today == N:
        return cur
    elif today > N:
        return 0
    else:
        return max(consult(today + 1, cur), consult(today + schedule_list[today][0], cur + schedule_list[today][1]))

사용한 함수이다.

만약 today가 딱 N 안으로 끝났다면 더 이상 추가할 수 없으니, 그냥 현재의 이익을 반환한다.

만약 today가 N을 벗어났다면, 해당 스케줄은 사용할 수 없는 스케줄이니 그냥 0을 반환해버린다.

위의 2가지 경우 모두 해당되지 않는다면, 해당 스케줄을 추가하는 것과 추가하지 않는 것을 다시 재귀함수에 넣어서 그 중 큰 값을 반환한다.

import sys

N = int(sys.stdin.readline())

schedule_list = []

for i in range(N):
    T, P = map(int, sys.stdin.readline().split())
    schedule_list.append([T, P])


def consult(today, cur):
    if today == N:
        return cur
    elif today > N:
        return 0
    else:
        return max(consult(today + 1, cur), consult(today + schedule_list[today][0], cur + schedule_list[today][1]))


print(consult(0, 0))

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

그냥 부분집합 만들고, 그 부분집합이 S인지 확인하면 끝난다.

물론 방법은 쉽지만, 경우가 많이 나오기 때문에 신경쓰지 않으면 시간초과가 날 거 같기도 하다.

딱히 생각나는 방법은 없어서 재귀함수로 풀었다.

def find(param_list, cur_num):
    if len(param_list) == 0:
        if cur_num == S:
            return 1
        else:
            return 0

    return find(param_list[1:], cur_num + param_list[0]) + find(param_list[1:], cur_num)

각 수마다 넣을 지 말지에 대해서 2가지 경우의 수로 나누고, 선택할 수 있는 수가 없을 때의 합을 구해서 S가 맞는 지 확인한다.

지금 작성하면서 보니까 cur_num을 안쓰고 그냥 sum(list)로 했으면 더 깔끔했을 거 같다.

이렇게 하면 길이가 5개 일 때, 32가지의 경우가 나오게 된다.

하지만 이렇게 구하면 답은 맞지 않을거다.

공집합의 경우의 수도 포함하여 0을 반환하기 때문에 해당 경우는 빼주어야 한다.

import sys

N, S = map(int, sys.stdin.readline().split())

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


def find(param_list, cur_num):
    if len(param_list) == 0:
        if cur_num == S:
            return 1
        else:
            return 0

    return find(param_list[1:], cur_num + param_list[0]) + find(param_list[1:], cur_num)


result = find(input_list, 0)

if S == 0:
    print(result - 1)
else:
    print(result)

공집합은 0이기 때문에 S가 0일 때만 빼주도록 하자.