greentea31's Note

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])

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

풀이 과정

문제를 보면 떠오르는건 주어진 자연수 N을 가장 큰 제곱수로 계속 빼나가는 그리디 방법이다.

7, 1, 4, 11, 13의 문제에서 주어진 모든 입력에서 그리디로 풀면 적절한 답이 나오므로 이게 정답일것 같지만 반례가 존재한다.

61 = 36 + 25로 N이 61일때 제곱항의 최소 수는 2인데 그리디로 풀면 49 + 9 + 1 + 1 + 1로 제곱항의 수가 5가 나온다.

d[i] => 자연수 i를 제곱수들의 합으로 표현할 때 제곱항의 최소 개수라고 하자. 그러면

d[i] = min(d[i-j*2]) + 1 (1 <= j*2 <= i) 라는 점화식이 성립한다.

소스 코드

import sys

N = int(sys.stdin.readline())
d = [i for i in range(100001)]
d[0] = 0

for i in range(2, N+1):
    j = 1
    while j*j <= i:
        if d[i] > d[i-j*j] + 1:
            d[i] = d[i-j*j] + 1
        j += 1

print(d[N])

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

풀이 과정

시간 제한 1초에 n이 최대 100,000이므로 브루트 포스로 합을 일일이 다 구하면 시간제한 내에 문제를 해결할 수 없을 것이다.

d[i] = i를 마지막으로 하는 가장 큰 연속합이라고 하자.

가장 큰 연속합을 구하기 위해서 맨 앞에서 부터 숫자를 쭉 더해나가되, 연속합이 0보다 작아지는 순간 기존의 수들의 합은 버리고 새로운 수부터 합을 구하는게 더 값이 커질 것임을 알 수 있다.

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

                  = A[i] (d[i-1] <= 0)

이라는 점화식이 성립하고 이를 통해 문제를 해결할 수 있다

소스 코드

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A.insert(0, 0)
d = [-1001 for _ in range(n+1)]
d[1] = A[1]

for i in range(2, n+1):
    d[i] = d[i-1] + A[i] if d[i-1] > 0 else A[i]

print(max(d))

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

풀이 과정

https://greentea31.tistory.com/34

위 문제에서 사용했던 식 D[i] = max(D[J]) + 1 (j < i, A[j] < A[i])으로 가장 긴 증가하는 부분 수열의 길이는 구할 수 있었지만, 이번 문제는 부분 수열 그 자체를 구해야 한다.

이를 위해서는 S[i] 배열을 하나 더 만들어서 D[i]를 계산할 때 쓰인 max(D[j])에서 max일때 쓰인 j를 저장하도록 하자. 그러면 가장 긴 증가하는 부분 수열의 길이가 가장 긴 D[i]에서 S 배열을 확인하면서 부분 수열의 index를 뒤에서 부터 확인할 수 있고, 이를 뒤집어서 출력해주면 가장 긴 증가하는 부분 수열 자체를 구할 수 있다.

예시는 다음과 같다.

소스 코드

import sys

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

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

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

for i in range(2, N+1):
    checkMaxLength = 0
    for j in range(1, i):
        if A[j] < A[i]:
            if checkMaxLength < d[j]:
                checkMaxLength = d[j]
                s[i] = j
    d[i] = checkMaxLength + 1

maxIndex = 0
maxValue = 0
for i in range(1, N+1):
    if maxValue < d[i]:
        maxValue = d[i]
        maxIndex = i

print(maxValue)
n = maxIndex
answer = []

while True:
    answer.append(A[n])
    n = s[n]
    if n == 0:
        break

answer.reverse()
print(' '.join(str(i) for i in answer))

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

풀이 과정

D[i] => A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이라고 하면,

이렇게 A[i]에 따른 D[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()))
A.insert(0, 0)

d = [1 for _ in range(len(A))]

for i in range(2, len(A)):
    checkMaxLength = 0
    for j in range(1, i):
        if A[j] < A[i]:
            checkMaxLength = max(checkMaxLength, d[j])
        d[i] = checkMaxLength + 1

print(max(d))

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

풀이 과정

D[n][k]를 k로 끝나는 n자리 이친수의 개수라고 하자

1이 두번 연속으로 나타나면 안된다는 문구를 보고 다음과 같은 2가지 방법을 생각할 수 있다.

    1. D[n][0] = D[n-1][0] + D[n-1][1], D[n][1] = D[n-1][0] 꼴로 2차원 배열로 해결하기.

    2. D[n] = D[n][0] + D[n][1] 이고 1번의 식에서 본 것 처럼 D[n][0] = D[n-1][0] + D[n-1][1] = D[n-1]이다. D[n][1]은 D[n-2]

        01을 뒤에 붙여서 만들 수 있으므로 D[n] = D[n-1] + D[n-2]가 성립한다. 따라서 1차원 배열로도 해결할 수 있다.

2번 방법을 사용해 문제를 해결하였다.

소스 코드

d = [0 for _ in range(0, 91)]
d[1] = 1
d[2] = 1
for i in range(3, 91):
    d[i] = d[i-1] + d[i-2]

N = int(input())
print(d[N])