# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Main ----------
N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
dp = [0] * (K+1)
dp[0] = 1
for coin in coins:
for k in range(coin, K+1):
dp[k] += dp[k-coin]
print(dp[-1])
# -------------------- Case 1 --------------------
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Function ----------
def DP(N):
if N == 1:
return 10
else:
dp = [1 for _ in range(10)]
for _ in range(2, N+1):
for i in range(1, 10):
dp[i] += dp[i-1]
return sum(dp)
# ---------- Main ----------
N = int(input())
result = DP(N)
print(result % 10007)
DP를 이용한 일반적인 풀이
# -------------------- Case 2 --------------------
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Function ----------
def factorial(n: int) -> int:
global dp
if n == 0 or n == 1:
return 1
if dp[n]:
return dp[n]
else:
dp[0], dp[1] = 1, 1
for i in range(2, n+1):
dp[i] = i * dp[i-1] % MOD
return dp[n]
def power(a: int, n: int) -> int:
if n == 0:
return 1
tmp = power(a, n//2)
if n % 2 == 0:
return tmp * tmp % MOD
else:
return tmp * tmp * a % MOD
# ---------- Main ----------
N = int(input()) + 9
K = 9
MOD = 10_007
dp = [0] * (N+1) # 팩토리얼 계산용 dynamic programming 리스트
numerator = factorial(N) # 분자
denominator = factorial(N-K) * factorial(K) % MOD # 분모
# 페르마의 소정리 이용
print(numerator * power(denominator, MOD-2) % MOD)
이런 식으로 나아가면서 앞의 수들을 더해가면 되네? 하는 생각으로 개수를 표로 표현해보았다.
규칙 표(왼쪽), 규칙 도식화(오른쪽)
길이(입력)이 4일 때, 끝자리가 6, 7, 8, 9일 때 적지 않은 것은 여기까지 적었을 때 규칙을 발견했기 때문이다.
왼쪽의 표 일부를 떼와서 오른쪽의 그림으로 도식화해보았다.
표 상에서 내 위의 수와, 내 왼쪽의 수 2개를 더하면 현재의 값이 완성된다.
만약 dp = [1 for _ in range(10)]의 배열이 있다고 가정해보자.
그럼 어떤 특정 위치의 값은 dp[i]일 것이다. 여기에 dp[i-1]만 더하면 코드는 완성이다.
1로 크기 10의 배열을 선언, 초기화한 뒤 입력받은 크기까지 반복문으로 돌면 코드는 간단하게 끝이 난다.
# -------------------- Case 1 --------------------
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Function ----------
def DP(N):
if N == 1:
return 10
else:
dp = [1 for _ in range(10)]
for _ in range(2, N+1):
for i in range(1, 10):
dp[i] += dp[i-1]
return sum(dp)
# ---------- Main ----------
N = int(input())
result = DP(N)
print(result % 10007)
N이 1일 경우에는 10으로 간단하게 return 해주고 끝을 낸다.
그 다음 2부터 N까지 더하는 연산을 진행해줘야 하기에 range(2, N+1)만큼 돈다.
그리고 1부터 9까지 dp의 값들을 업데이트 해줘야 하기에 range(1, 10)만큼 돈다.
왜 0부터가 아니냐고? 0번째 인덱스, 즉 끝자리가 0인 값은 길이가 어떻든 무조건 1개이기 때문이다.
그리고 마지막으로 합(sum)을 10007로 나눈 나머지를 구하면 정답이다.
눈치가 빠르다면 위의 코드에서 Case 1이라고 쓴 것을 봤을 것이다.
난 위의 표에서 한 가지를 더 발견했다.
안 보이는가??? 수학자들이 환장하는 그 수들이?! 파스칼의 삼각형이!!!
정말이지 흥분하지 않을 수 없다.
간단해보이지만 그렇지 않은 이 DP 문제에서 파스칼의 삼각형이라니!
피보나치도, 시어핀스키 삼각형도, 삼각수도, 사면체수도, 이항계수도, 자연수도 모든 게 표현 가능한
파스칼의 삼각형이라니!!! 이건 분명 더 간단하게 풀 수 있는 무언가가 있다는 직감이 왔다.
파스칼의 삼각형을 이용한 오르막 수(왼쪽), 파스칼의 삼각형 하키스틱 패턴(오른쪽)
길이가 1, 2, 3일 때를 각각 주황색, 초록색, 하늘색으로 칠해보았다.
물론 우하향의 대각선을 칠하기는 했지만, 좌하향의 대각선을 칠해도 상관없다.
왜? 파스칼의 삼각형이니까!
원하는 길이(행)에서부터 대각선으로 딱 10개만 더하면 우리가 구하고자 하는 식(값)이 나온다.
이걸 어떤 방법으로 구하면 좋을까 생각을 하다 하키스틱 패턴을 생각했다.
하키스틱 패턴은 어떤 부분이든 한 변에서 시작해 쭉 직진하다가, 한 번 꺾는 순간, 직진의 합이 꺾은 수와 동일하다.
연두색으로 칠한 예시를 보자. 1 + 8 + 36 + 120은 165이다. 궁금하다면 직접 더 해보자.
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Main ----------
N = int(input())
cache = [-1001] * (N+1)
list_N = [0] + list(map(int, input().split()))
for i in range(1, N+1):
cache[i] = max(list_N[i], list_N[i] + cache[i-1])
print(max(cache))
# ---------- Comment ----------
# max(list_N[i], list_N[i] + cache[i-1])
# 이제껏 더한 수와, 현재 배열의 수 중 더 큰 값을 찾는다.
# 위에서 언급한 방법 의사 코드
for LEN in range(1, len(arr)+1): # 연속된 수의 길이
for INDEX in range(len(arr) - LEN): # 연속된 수의 합 시작점
for문으로 LEN 길이만큼 더하기 # 연속된 수 더하기
if MAXNUM = 가장 큰 값 # 가장 큰 값 판별하기
음...이건 아니다. 이렇게만 봐도 시간복잡도가 O(n4)를 넘는다.
이건 동적 계획법이 아니라 브루트 포스에 더 가깝다. 조금 더 세련된 방법이 필요하다.
동적 계획법은 작은 문제로 나누어, 과거에 구한 값을 활용하는 방식임을 생각해보자.
우선 가장 큰 값을 활용해야 하니, 어떤 두 값을 비교하여 최댓값을 저장한다.
그리고 이 최댓값을 불러와서 다시 비교한다.
이런 식으로 작성하면 될 것 같은 느낌이 들었다.
for i in arr:
tmp[i] = tmp[i-1]+arr[i]와 arr[i] 중 더 큰 값
여기서 핵심은 과거에 구한 값을 활용하는 것이다.
이전의 값들을 더해서 tmp에 저장하고, 그것을 새로운 값과 비교하여 다시 더한다.
이렇게 하면 계속해서 연속된 값을 유지할 수 있다.
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Main ----------
N = int(input())
cache = [-1001] * (N+1)
list_N = [0] + list(map(int, input().split()))
for i in range(1, N+1):
cache[i] = max(list_N[i], list_N[i] + cache[i-1])
print(max(cache))
# ---------- Comment ----------
# max(list_N[i], list_N[i] + cache[i-1])
# 이제껏 더한 수와, 현재 배열의 수 중 더 큰 값을 찾는다.
이런 식으로 작성하면 연속된 값들 중 가장 큰 값을 얻을 수 있다.
처음에연속하는 길이가 얼마인지에 대한 고민을 조금 많이 했었는데 별로 중요하지 않았다.
결국 중요한 것은 출력이 가장 큰 값이다.
주어진 입력은 list_N에 저장하였고, 임의로 저장하는 배열은 cache로 선언했다.
list_N의 0번째 인덱스를 0을 넣어준 이유는 계산을 편하게 하기 위함이다.
cache를 -1001로 초기화한 이유는 조건이 "수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다."이기 때문이다.
# ---------- Function ----------
def padovan(N):
#padovan_list[1], padovan_list[2], padovan_list[3] = 1, 1, 1
if N == 1 or N == 2 or N == 3:
return 1
if padovan_list[N] != 0:
return padovan_list[N]
padovan_list[N] = padovan(N-2) + padovan(N-3)
return padovan_list[N]
# ---------- Main ----------
caseT = int(input())
for _ in range(caseT):
N = int(input())
padovan_list = [0] * (N+1)
print(padovan(N))
padovan(N) 함수를 살펴보면 1, 2, 3항은 전부 1이므로 1로 초기화한다.
그후 padovan 리스트의 N번째 인덱스 값이 비어있다면 padovan(N-2)와 padovan(N-3)을 호출한다.
10번쨰 코드인 "padovan_list[N] = padovan(N-2) + padovan(N-3)" 부분이 핵심이다.
