dp인건 알겠는데 어디서 계산이 틀린 부분이 있는지 한참을 안되다가 다시 해보니까 3분만에 풀림 이것이 인생 1. 거스름돈 1,2,5원 중 1원을 낼 수 있는 것 다 더해주고 그다음 2원으로 계산되는 것 다 내준다. 그 다음 5원 순으로 더한다 배열 말고 그냥 dict을 사용했고 from collections import defaultdict def solution(n, money): dp=defaultdict(int) dp[0]=1 for m in money: for i in range(m,n+1): dp[i]+=dp[i-m]%1000000007 return dp[n] 2. 자바스크립트 function solution(n, money) { var answer = 0; let dp=new Array(n+..
dp[n] 번째 타일을 만드는 경우의 수는 1. dp[n-2] 번째 타일들에 세로 방향 타일 하나를 붙이는 경우 2. dp[n-1]번째 타일들에 가로 방향 2개의 타일을 붙이는 경우 2 가지를 합친 방법이다 def solution(n): a,b=1,2 for i in range(3,n+1): a,b=b,(a+b)%1000000007 return b
가끔 나오는 유형이다. 자체 배열을 지금까지의 합을 담은 dp배열 처럼 쓰는 형식의 dp문제 def solution(t): for i in range(1,len(t)): for j in range(0,i+1): if j==0: t[i][j]+=t[i-1][0] elif j==i: t[i][j]+=t[i-1][i-1] else: t[i][j]=max(t[i][j]+t[i-1][j-1],t[i][j]+t[i-1][j]) return max(t[len(t)-1])
def solution(board): for i in range(1,len(board)): for j in range(1,len(board[0])): if board[i][j]==1: board[i][j]=min([board[i-1][j-1],board[i][j-1],board[i-1][j]])+1 # 이런식으로 쭉 늘여놓을 수 있는 듯 return max([item for row in board for item in row])**2