NOTES

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

Description

아래와 같이 나선형으로 정삼각형을 그려나간다. (1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12) 

n번째 삼각형의 한 변의 길이를 구하라.

Idea

Code

a = [1, 1, 1, 2, 2]

for _ in range(95):
	# a_n = a_(n-1) + a_(n-5)
	a.append(a[-1] + a[-5])

for _ in range(int(input())):
	print(a[int(input()) - 1])

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

Description

Idea

Code

scores = [int(input()) for _ in range(int(input()))]
# zero : highest score when the one does not choice the last wine
# one : highest score when the one choice the last wine, but not the previous one
# two : highest score when the one choice the last wine and the previous one
# define initial conditions
zero, one, two = 0, scores[0], 0

# starting from index 1, iterate through last wine
for score in scores[1:]:
	zero, one, two = max(zero, one, two), zero + score, one + score

print(max(zero, one, two))
	

Description

Idea

Pseudocode

1. dp[i - value] ( i > value )
2. 0 ( i = value )
3. inf ( i < value )

Code

def solve(k, dp, values):
    for i in range(1, k+1):
        dp[i] = min([case(i, dp, value) for value in values]) + 1

    return [dp[k], -1][dp[k] == 10000]

def case(i, dp, value):
    if i > value:
        return dp[i - value]
    elif i == value:
        return 0
    else:
        return 10000

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 = [10000] * (k+1)

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

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

Description

1.  한 번에 한 계단 또는 두 계단만 이동 가능
2. 연속된 세 계단을 모두 밟아서는 안 됨. 시작점은 포함하지 않음.
3. 마지막 계단은 꼭 밟아야

Idea

Code

def maxScoreFinalOneStep(n, dp1, dp2, scores):
    ''' computes max score when the one gets to nth step with final one-up-step '''
    #
    #base cases
    #

    #0th step : score 0
    if n == 0 and dp1[n] == -1:
        dp1[n] = 0
        return dp1[n]
    #1st step : score[1]
    elif n == 1 and dp1[n] == -1:
        dp1[n] = scores[n]
        return dp1[n]
    #2nd step : score[1] + score[2]
    elif n == 2 and dp1[n] == -1:
        dp1[n] = scores[n-1] + scores[n]
        return dp1[n]
    
    #dp2[n-1] not set, compute it
    if dp2[n-1] == -1:
        dp2[n-1] = maxScoreFinalTwoStep(n-1, dp1, dp2, scores)
    
    #finally fill in dp1[n] and return it
    dp1[n] = dp2[n-1] + scores[n]
    return dp1[n]

def maxScoreFinalTwoStep(n, dp1, dp2, scores):
    ''' computes max score when the one gets to nth step with final two-up-step '''
    #
    #base cases
    #

    #0th step : score 0
    if n == 0 and dp2[n] == -1:
        dp2[n] = 0
        return dp2[n]
    #1st step : score 0. we cannot reach 1st step with final two-up-step
    elif n == 1 and dp2[n] == -1:
        dp2[n] = 0
        return dp2[n]
    #2nd step : scores[2]
    elif n == 2 and dp2[n] == -1:
        dp2[n] = scores[n]
        return dp2[n]

    #if dp1[n-2] or dp2[n-2] not set, fill them in
    if dp1[n-2] == -1:
        maxScoreFinalOneStep(n-2, dp1, dp2, scores)
    if dp2[n-2] == -1:
        maxScoreFinalTwoStep(n-2, dp1, dp2, scores)

    #finally fill in dp2[n] and return it
    dp2[n] = max(dp1[n-2], dp2[n-2]) + scores[n]
    return dp2[n]

if __name__ == '__main__':
    #total number of steps
    N = int(input())
    #scores of each steps. 0th step has 0 score!
    scores = [0] + [int(input()) for _ in range(N)]

    #dp1[n] : max score when reaches nth step with final one-up-step
    dp1 = [-1] * (N+1)
    #dp2[n] : max score when reaches nth step with final two-up-step
    dp2 = [-1] * (N+1)

    #answer
    print(max(maxScoreFinalOneStep(N, dp1, dp2, scores), maxScoreFinalTwoStep(N, dp1, dp2, scores)))