greentea31's Note

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

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

풀이 과정

D[n][k] => 마지막이 k로 끝나는 n자리 계단수의 개수라고 하자

모든 인접한 자리의 차이가 1이어야 한다는 점을 고려하면 다음과 같은 점화식을 생각할 수 있다

D[n][0] = D[n-1][1]

D[n][k] = D[n-1][k-1] + D[n-1][k+1] (1 <= k <= 8)

D[n][9] = D[n-1][8]

이를 통해 문제를 해결할 수 있다

소스 코드

N = int(input())
d = [0, [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

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

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

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

풀이 과정

https://greentea31.tistory.com/28

위의 문제에서 같은 수를 2번 연속으로 사용하면 안된다는 조건만 추가되었다.

D[n][k] => 정수 n을 마지막이 k로 끝나게끔 합으로 나타내는 경우의 수라고 하자.

그렇다면 k에 따라 점화식을 달리 해서 같은 수가 2번 연속으로 나타나지 않도록 조정이 가능하다.

D[n][1] = D[n-1][2] + D[n-1][3]

D[n][2] = D[n-2][1] + D[n-2][3]

D[n][3] + D[n-3][1] + D[n-3][2]

소스 코드

import sys

T = int(sys.stdin.readline())
d = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 1, 1, 1]]
for i in range(4, 100001):
    d.append([0, (d[i-1][2] + d[i-1][3]) % 1000000009, (d[i-2][1] + d[i-2][3]) % 1000000009, (d[i-3][1] + d[i-3][2]) % 1000000009])
for _ in range(T):
    n = int(sys.stdin.readline())
    print(sum(d[n]) % 1000000009)

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

풀이 과정

https://greentea31.tistory.com/29

위의 문제의 점화식에서 max만 min으로 바꿔주면 되는 문제이다

D[n]을 n개의 카드를 주어진 카드팩을 통해 가장 싸게 구매할 때 지불해야 할 가격이라고 하자.

D[n] = min(D[n-k] + P[k]) (1 <= k <= n)

위의 점화식을 통해 문제를 해결하되, 리스트의 초기값을 큰 수로 잡아놔야 원하는 결과를 얻을 수 있음을 고려해야 한다.

소스 코드

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
d = [0]
P.insert(0, 0)

for i in range(1, N+1):
    minValue = 10000001
    for j in range(1, i+1):
        minValue = min(minValue, d[i-j] + P[j])
    d.append(minValue)

print(d[N])

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

풀이 과정

D[n]을 n개의 카드를 주어진 카드팩으로 가장 비싸게 살 때의 지불해야 하는 가격이라고 하자.

D[n] = max(D[n-1] + P[1], D[n-2] + P[2], D[n-3] + p[3] ...)

D[n] = max(D[n-k] + P[k]) (1 <= k <= n) 이라는 점화식이 성립한다.

소스 코드

import sys

N = int(sys.stdin.readline())
P = list(map(int, sys.stdin.readline().split()))
d = [0]
P.insert(0, 0)

for i in range(1, N+1):
    maxValue = 0
    for j in range(1, i+1):
        maxValue = max(maxValue, d[i-j] + P[j])
    d.append(maxValue)

print(d[N])

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

풀이 과정

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 d[n]이라고 하자

n-3을 나타내는 1, 2, 3의 합으로 이루어진 식에 +3을 해주면 정수 n을 나타내고,

n-2을 나타내는 1, 2, 3의 합으로 이루어진 식에 +2을 해주면 정수 n을 나타내고,

n-1을 나타내는 1, 2, 3의 합으로 이루어진 식에 +1을 해주면 정수 n을 나타낸다

따라서, d[n] = d[n-3] + d[n-2] + d[n-1]이라는 점화식이 성립한다 

소스 코드

import sys
T = int(sys.stdin.readline())

for _ in range(T):
    n = int(input())
    d = [0, 1, 2, 4]
    for i in range(4, n+1):
        d.append(d[i-1] + d[i-2] + d[i-3])
    print(d[n])