✅ 문제 풀이 - BOJ (DP)
🎈 15988 1, 2, 3 더하기 3
정수 N이 주어졌을 때 1, 2, 3 수들의 합으로 N을 나타내는 방법의 수를 구하는 문제
첫줄에 테스트 케이스 수 T가 주어지고 T줄만큼 정수 N이 주어져 각 N을 1,2,3 합의 조합으로 만들 수 있는 방법의 수를 구하면 된다.
import sys
input = sys.stdin.readline
dp = [1,2,4,7]
t = int(input())
for i in range(t):
n = int(input())
for j in range(len(dp), n):
dp.append((dp[-3] + dp[-2] + dp[-1]) % 1000000009)
print(dp[n-1])< 풀이 과정 >
n을 7까지 구현해보면 점화식은 다음과 같다
- dp[n] = dp[n-3] + dp[n-2] + dp[n-1]
따라서 이를 그대로 리스트로 구현해준 풀이
🎈 1965 상자 넣기
첫 줄에 상자 수가 주어지고, 둘째 줄의 각 상자 별 크기들이 주어진다.
앞 상자 크기보다 뒷 상자의 크기가 더 클 경우 상자를 합칠 수 있는데 이때, 최대로 합칠 수 있는 상자 개수를 구하는 문제
import sys
input = sys.stdin.readline
n = int(input())
box = list(map(int, input().split()))
dp = [1] * len(box)
for i in range(len(box)):
for j in range(i):
if box[i] > box[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))< 풀이 과정 >
상자 수 n과 상자 크기 리스트 box를 생성하고 dp를 1개씩 box 길이만큼의 리스트로 만들어준다.
그 이후 box리스트에서 앞 상자 보다 뒷 상자 크기가 더 크면 + 1씩 진행하여 dp로 저장하면 되므로, 주어진 조건에 맞춘 후 dp[i]를 dp[i]와 dp[j]+1 값 중 더 큰 값으로 비교해가며 update 후 max값을 출력해준다.
🎈 14002 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열을 구하는 프로그램 작성하기
예를 들어 수열 A = {10, 20, 10, 30, 20, 50} 인 경우,
가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
최종적으로 길이와 각 증가되는 원소를 출력해주면 되는 문제
import sys
input = sys.stdin.readline
n = int(input())
seq = list(map(int, input().split()))
length = [1] * len(seq)
answer = []
for i in range(n):
for j in range(i):
if seq[i] > seq[j]:
length[i] = max(length[i], length[j] + 1)
print(max(length))
sequence = []
maxi = max(length)
for i in range(n-1, -1, -1):
if length[i] == maxi:
sequence.append(seq[i])
maxi -= 1
sequence.sort()
print(*sequence)< 풀이 과정 >
n과 수열 A를 seq로 나타낸 리스트를 만들어주고, 증가되는 부분의 길이와 원소를 나열하면 되는 문제.
길이와 원소를 스택으로 구현하거나 dp를 활용하여 하나의 리스트로 결과를 생성하려했지만 실패🙄
길이와 원소를 다른 리스트로 구분하여 해결할 수 있었다.
- length 리스트는 원소가 각 1개씩 각 위치 별로 존재하므로 1의 값을 n개만큼 가지도록 처리한 이후 2중 for문을 활용해 이전 원소보다 지금 더 크면 값을 늘리는 식으로 최대길이를 출력해준다.
- 앞서 만든 length를 바탕으로 거꾸로 탐색하며 최대값과 일치하면 sequence 리스트에 수열 A원소를 추가해주며 반복하고 최대값을 1씩 낮추며 반복한다.
최종적으로 거꾸로 탐색하였으므로 sort (오름차순) 정렬하여 원소만 출력한다.
