greentea31's Note

https://greentea31.tistory.com/36

풀이 과정

https://greentea31.tistory.com/36

위의 연속합 문제에서 수열에서 수를 하나 제거할 수 있다는 조건이 추가된 문제이다. 

d[i]를 i번째 원소를 마지막으로 하는 가장 큰 연속합이라 하고, d2[i]를 i번째 원소에서 시작하는 가장 큰 연속합이라 하자. 그렇다면 i번째 원소를 제거했을 경우의 연속합을 구하면 d[i-1] + d2[i+1] 임을 알 수 있다.

d[i]의 점화식은 위의 문제를 풀어봤다면,

d[i] = d[i-1] + a[i] (d[i-1] > 0)

       = A[i] (d[i-1] <= 0) 임을 알 수 있고,

d2[i]의 점화식은 위의 점화식을 조금 변형한

d2[i] = d2[i+1] + a[i] (d2[i+1] >= 0)

         =  a[i] (d2[i+1] < 0) 임을 알 수 있다.

수열의 모든 원소 i에 대해 d[i], d[i-1] + d2[i+1]을 구해보고 구한 값들 중 가장 큰 값을 정답으로 출력해주면 된다.

소스 코드

import sys

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

d = [i for i in A]
d2 = [i for i in A]

for i in range(1, n):
    d[i] = max(d[i-1] + A[i], A[i])

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

max1 = max(d)
max2 = -1001

for i in range(1, n-1):
    max2 = max(max2, d[i-1] + d2[i+1])

print(max(max1, max2))

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

풀이 과정

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라 한다.

그렇다면 Sk를 기준으로 하는 바이토닉 수열의 길이는 Sk를 마지막으로 하는 증가하는 부분 수열의 길이 + Sk를 시작으로 하는 감소하는 부분 수열의 길이 - 1임을 알 수 있다.

따라서 주어진 수열의 모든 원소 K에 대해 K를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 + K를 시작으로 하는 가장 긴 감소하는 부분수열의 길이 - 1을 구한 뒤, 가장 긴 값이 바로 가장 긴 바이토닉 부분 수열의 길이이다.

https://greentea31.tistory.com/34

https://greentea31.tistory.com/62

이 문제는 위의 2문제의 풀이법을 합쳐서 해결할 수 있는 문제이고 각 문제의 풀이를 위한 점화식은 위의 두 글을 참고하면 된다.

소스 코드

import sys

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

d = [1 for _ in range(N)]
d2 = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] < A[i]:
            d[i] = max(d[i], d[j] + 1)

for i in range(N-1, -1, -1):
    for j in range(N-1, i, -1):
        if A[j] < A[i]:
            d2[i] = max(d2[i], d2[j] + 1)

d3 = [d[i] + d2[i] - 1 for i in range(N)]

print(max(d3))

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

풀이 과정

https://greentea31.tistory.com/34

가장 긴 증가하는 부분 수열 -> 가장 긴 감소하는 부분 수열임을 제외하면 위의 문제의 해결법과 풀이과정이 일치한다.

가장 긴 증가하는 부분 수열을 구하는 점화식

D[i] = max(D[J]) + 1 (j < i, A[j] < A[i])

에서 부등호만 다음과 같이 바꿔주고 코드로 구현하면 문제를 해결할 수 있다.

D[i] = max(D[J]) + 1 (j < i, A[j] > A[i])

소스 코드

import sys

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

d = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if A[j] > A[i]:
            d[i] = max(d[i], d[j] + 1)

print(max(d))

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

풀이 과정

https://greentea31.tistory.com/34

11053번 문제와 비슷한 점화식을 세워서 문제를 해결할 수 있다.

sum[i] -> i번째 원소를 마지막으로 하는 합이 가장 큰 증가 부분수열 이라고 하면 다음과 같은 점화식이 성립한다.

sum[i] = max(sum[j]) + A[i] (j < i, A[j] < A[i])

소스 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
sum = [x for x in A]

for i in range(n):
    for j in range(i):
        if A[j] < A[i]:
            sum[i] = max(sum[i], sum[j] + A[i])

print(max(sum))

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

풀이 과정

정수 삼각형에 들어있는 요소를 담는 배열을 위의 그림과 같이 생각하면

d[i][0] = d[i-1][0] + p[i][0]

d[i][k] = max(d[i-1][k-1] + p[i][k], d[i-1][k] + p[i][k]) (1  <= k <= i-1)

d[i][i] = d[i-1][i-1] + p[i]

다음과 같은 점화식이 성립하고 이를 통해 문제를 해결하면 된다

소스 코드

import sys

n = int(sys.stdin.readline())
p = []
d = []

for i in range(n):
    p.append(list(map(int, sys.stdin.readline().split())))
    if i == 0:
        d.append([p[0][0]])
        continue
    d.append([d[i-1][0] + p[i][0]])
    for k in range(1, i):
        d[i].append(max(d[i - 1][k - 1], d[i - 1][k]) + p[i][k])
    d[i].append(d[i-1][i-1] + p[i][i])

print(max(d[n-1]))

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

풀이 과정

있는 포도주를 최대로 마시고 싶은데 3잔 연속으로는 마실수 없다는 조건이 걸려있는 문제이다.

0번째 연속, 1번째 연속, 2번째 연속으로 마신 경우를 나누어서 고려해 3번째 연속으로 마시는 경우가 나올수 없게 하자.

d[i]를 i번째 까지 마셨을 때의 마신 포도주의 최대 값이라고 하고, p[i]를 i번째 포도주 잔에 들어있는 포도주의 양이라고 하자.

0번째 연속으로 마신 경우: d[i-1]

1번째 연속으로 마신 경우: d[i-2] + p[i]

2번째 연속으로 마신 경우: d[i-3] + p[i-1] + p[i]이 성립한다.

위의 점화식을 이용해 문제를 해결할 수 있다.

소스 코드

import sys

n = int(sys.stdin.readline())
p = []

for _ in range(n):
    p.append(int(sys.stdin.readline()))

d = [p[0], p[0] + p[1] if n > 1 else 0, max(p[0] + p[2], p[1] + p[2], p[0] + p[1]) if n > 2 else 0]

for i in range(3, n):
    d.append(max(d[i-3] + p[i-1] + p[i], d[i-2] + p[i], d[i-1]))

print(d[n-1])

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

풀이 과정

d[i][k]를 k로 끝나는 i자리 오르막 수의 개수라고 하자.

d[i][k] = sum(d[N-1][j]) (0 <= j <= k) 가 성립한다.

소스 코드

import sys
mod = 10007

d = [[0 for _ in range(0, 10)] for __ in range(0, 1001)]
d[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

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

for i in range(2, N+1):
    for j in range(0, 10):
        for k in range(0, j+1):
            d[i][j] += d[i-1][k]
            d[i][j] %= mod

print(sum(d[N]) % mod)

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

풀이 과정

d[i][k]를 2xi 우리에 사자를 가두는 경우의 수라고 하자. k = 0, 1, 2는 마지막 i번째 행에 사자가 없거나, 왼쪽에 있거나, 오른쪽에 있는 경우이다.

그러면,

d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2]

d[i][1] = d[i-1][0] + d[i-1][2]

d[i][2] = d[i-1][0] + d[i-1][1]

의 점화식이 성립한다

소스 코드

"""
가로 세로 인접 x, 몇가지?

0, 1, 2 안두기 왼쪽 오른쪽, 9901은 나머지 처리 잘하기

"""

import sys

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

d = [[0, 0, 0], [1, 1, 1]]
for i in range(2, N+1):
    d.append([(d[i-1][0] + d[i-1][1] + d[i-1][2]) % mod, (d[i-1][0] + d[i-1][2]) % mod, (d[i-1][0] + d[i-1][1]) % mod])

print(sum(d[N]) % mod)

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

풀이 과정

d[i][k]를 총 i개의 집을 조건에 맞게 칠하는 비용의 최소값이되 마지막이 k로 칠해지는 경우라고 하자. (0 = 빨강, 1 = 초록, 2 = 파랑)

그러면 다음과 같은 점화식이 성립한다.

d[i][0] = min(d[i-1][1], d[i-1][2]) + p[i][0]

d[i][1] = min(d[i-1][0], d[i-1][2]) + p[i][1]

d[i][2] = min(d[i-1][0], d[i-1][1]) + p[i][2]

소스 코드

import sys

N = int(sys.stdin.readline())
d = [[0 for _ in range(4)] for _ in range(N+1)]
p = [[0, 0, 0]]

for i in range(1, N+1):
    p.append(list(map(int, sys.stdin.readline().split())))
    d[i] = p[i]
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + p[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + p[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + p[i][2]

print(min(d[N]))

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

풀이 과정

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

이 문제와 푸는 방법이 동일하나 들어올 수 있는 입력 n의 최대값이 11에서 10억 9라는 큰 숫자로 늘었다. 나머지 연산을 통해 오버플로우의 발생을 방지해야 한다.

(A+B+C) % M = ((A%M) + (B%M) + (C%M)) % M임을 이용해 계산 도중 숫자가 너무 커지지 않게 나머지 연산 처리를 적절히 끊어서 해주면 된다. 단 그래도 10억이 3번 더해지는 경우가 생길 수 있고, 이 경우에 int형 타입의 최대값인 2,147,483,647을 넘을수도 있으므로 unsigned int형태로 문제를 푸는 것이 좋지만 이건 c++등의 타 언어에서 고려해야 할 사항이고 파이썬에서는 그냥 int가 아주 큰 수도 처리할 수 있으므로 그냥 점화식을 통해 문제를 해결하면 된다.

d[i]를 정수 i를 1, 2, 3의 합으로 나타내는 경우의 수라고 하면

d[i] = d[i-1] + d[i-2] + d[i-3]이 성립한다.

소스 코드

import sys

mod = 1000000009
maximum_range = 1000001

T = int(sys.stdin.readline())
d = [0, 1, 2, 4]

for i in range(4, maximum_range):
    d.append(d[i-1] + d[i-2] + d[i-3])
    d[i] %= mod

for i in range(T):
    n = int(sys.stdin.readline())
    print(d[n])