동적 프로그래밍(dynamic programing)
지난 계단 오르기 문제(참고)를 풀어보며
동적 프로그래밍은 각 단계의 최적값을 메모리에 기록하여 중복 연산을 줄이는 기법이라고 이해했다.
그 이해를 바탕으로 오늘은 1912번 연속합 문제를 풀어보았다.
문제 1 - 연속합
배열이 주어졌을 때, 가장 큰 부분합을 구하는 것이다.
처음에는 그냥 양수일 경우 연속으로 더하고 음수일 경우 리셋이 되도록 했다.
첫번째 케이스는 통과였지만, 음수의 절대값이 양수의 절대값보다 큰 모든 경우에는 오답이 나왔다.
그래서 각 단계의 최적 값을 기록해가는 dp식 사고방식으로 고민해보았고,
각 인덱스 위치마다 최적의 합을 기록해가면 되겠다고 방향을 잡았다.
그런 다음, 모든 인덱스의 최적합 중 가장 큰 것을 출력하면 되지 않을까?
풀이
import sys
N = int(input())
array = list(map(int, sys.stdin.readline().split(' ')))
dp = [0] * N
dp[0] = array[0]
for n in range(1, N):
dp[n] = max(dp[n-1]+array[n], array[n])
print(max(dp))문제 2 - 1로 만들기
이 문제는 n에서부터 1까지 각 숫자가 나오는 최소 연산을 기록해놓으며 값을 줄여가자고 생각했다.
그래서 for 문을 거꾸로 돌렸고, 최대 연산 수는 1씩 빼는 n이 될테니 메모리(dp 배열)에는 n을 n+1의 길이만큼 넣어놓았다.
최소 연산수를 구하는 경우는 3배수, 2배수가 있었는지 여부를 확인해서 세가지 경우
3배수가 있는 경우 - 3배 값의 연산 수, 2배 값의 연산수, 앞의 값의 연산 수 중 최솟값 + 1
2배수는 있고 3배수는 없는 경우 - 2배 값의 연산수, 앞의 값의 연산 수 중 최솟값 + 1
2배수도 없는 경우 - 앞의 수에서 1빼는 연산만 가능하므로 앞의 값의 연순 수 + 1을 채워갔다.
마지막까지 한 경우, 인덱스 1의 값 == 1이 되는 연산 중 최솟값이므로
dp[1]을 출력해주었다.
풀이
n = int(input())
arr = [n]*(n+1)
arr[n] = 0
for i in range(n-1, 0, -1):
if i * 3 <= n:
arr[i] = min(arr[i*3], arr[i*2], arr[i+1]) + 1
elif i * 2 <= n and i*3 > n:
arr[i] = min(arr[i*2], arr[i+1]) + 1
elif i * 2 > n:
arr[i] = arr[i+1] + 1
print(arr[1])문제 3 - 쉬운 계단 수
이 문제는 최적의 값을 찾는 문제는 아니지만, 단순 반복 계산을 막기 위해 메모리를 사용하는 문제다.
가장 처음 생각한 아이디어는 길이가 1일때, 2일때, 3일때 가능한 계단 수를 기록해가면 n일때 구할 수 있지 않을까 했다.
하지만 코드를 적다보니, 0과 9일 때는 갈 수 있는 계단이 하나이고, 나머지 경우에는 계단이 2개니까 케이스를 나눠야 된다는 것을 깨달았다.
하지만 각 길이의 케이스마다 0으로 끝나는 개수, 9로 끝나는 개수를 알려면 모든 문자열을 저장해놓는 방법을 써야하는데, 메모리 초과 혹은 시간 초과가 발생할 수 있다.
그래서 각 문자열 길이마다 0~9로 끝나는 계단 수를 기록하기로 하고 이차원 배열로 구현해보았다.
이것이 최적의 솔루션이라는 확신은 없지만
동적 프로그래밍은 문제 해결 기법으로 풀이는 무한하다고 하니까 나의 솔루션은 이것으로 하겠다.
풀이
n = int(input())
arr = [[0,1,1,1,1,1,1,1,1,1] for _ in range(n)]
for i in range(1, n):
arr[i][0] = arr[i-1][1]
for j in range(1, 9):
arr[i][j] = arr[i-1][j+1] + arr[i-1][j-1]
arr[i][9] = arr[i-1][8]
print(sum(arr[-1])%1000000000)