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

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

Description

n가지 가치가 다른 종류의 동전이 있다. 가치의 합이 k원이 되면서 동전의 개수가 최소가 되는 경우를 찾는 문제이다. 동전의 개수의 최솟값을 출력하고 불가능하면 -1을 출력한다.

Idea

dp[k] : k원을 만드는데 필요한 최소 동전 수 dp[k]는 k보다 작은 dp값들로부터 구해질 수 있어서, k 값이 1일때부터 k일때까지 차례로 올라가면 된다.

Pseudocode

for i : 1 ~ k dp[i] = 1 + min(

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

for value in values) i = value 일때 0값을 갖는 이유는 결국 1을 더해주어 dp[i] 값이 1이 되게 하기 위함이다.

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