NOTES

Description

7

3    8

8    1    0

2    7    4    4

4    5    2    6    5

층 수 n 과 각 층의 숫자가 주어진다. 최댓값을 구하면 된다.

Idea

2차원 list로 하면 index 처리가 간단해지지만 memory overhead가 크다. 1차원 list로 풀어보자.

총 [latex]n(n+1)/2[/latex]개의 숫자가 존재하므로,

dp <- [-1] * n(n+1)/2로 초기화한다.

각 층의 숫자는 triangle이라는 list에 저장한다.

Pseudocode

for i: 0~n-1

for j:0~i

ind = i(i+1)/2 + j

dp[ind] =

1. dp[i(i-1)/2] + triangle[ind]  ( j = 0 )
2. dp[i(i-1)/2 + j - 1] + triangle[ind] ( j = i )
3. max(dp[i(i-1)/2 + j - 1], dp[i(i-1)/2 + j]) + triangle[ind] ( j = 나머지 )

Code

def solve(triangle, dp, n):
    solveHelper(triangle, dp, n)
    return max([dp[n*(n-1)//2 + j] for j in range(n)])

def solveHelper(triangle, dp, n):
    dp[0] = triangle[0]

    for i in range(1, n):
        for j in range(i+1):
            ind = i*(i+1)//2 + j
            # case 1 : leftmost number of a row
            if j == 0:
                dp[ind] = dp[i*(i-1)//2] + triangle[ind]
            # case 2: rightmost number of a row
            elif j == i:
                dp[ind] = dp[i*(i-1)//2 + j - 1] + triangle[ind]
            # case 3: middle
            else:
                dp[ind] = max(dp[i*(i-1)//2 + j - 1], dp[i*(i-1)//2 + j]) + triangle[ind]

if __name__ == '__main__':
    n = int(input())

    triangle = []
    for i in range(n):
        triangle += [int(v) for v in input().strip().split()]

    dp = [-1] * (n*(n+1)//2)
    print(solve(triangle, dp, n))

Description

Idea

Code

print("".join([c for c in input() if c.isupper()]))

Description

Idea

1. i < values[j] 일때 : dp[i][j] = 0
2. i =values[j] 일때 : dp[i][j] = 1
3. i > values[j] 일때 : dp[i][j] = dp[i - j][0] + dp[i - j][1] + ... + dp[i - j][j]

Code

def solve(k, dp, values):
    #rowwise iteration through dp (it is k * n 2d list!)
    for i in range(k+1):
        for j in range(len(values)):
            #case 1 : i < values[j] -> dp[i][j] = 0
            if i < values[j]:
                dp[i][j] = 0
            #case 2 : i == values[j] -> dp[i][j] = 1
            elif i == values[j]:
                dp[i][j] = 1
            #case 3 : i > values[j] -> dp[i][j] = sum(dp[i-values[j]][0, 1, ..., j])
            else:
                dp[i][j] = sum([dp[i-values[j]][x] for x in range(j+1)])

    return sum([dp[k][x] for x in range(len(values))])


if __name__ == '__main__':
    #parse input
    n, k = [int(i) for i in input().split()]
    values = [int(input()) for _ in range(n)]

    #make dp list
    dp = [[-1] * n for _ in range(k+1)]

    #answer
    print(solve(k, dp, values))