코딩 테스트/다이나믹 프로그래밍10 편집 거리 p. 382 str1=input() str2=input() n=len(str1) m=len(str2) d=[[0]*(m+1) for _ in range(n+1)] for i in range(1,n+1): d[i][0]=i for i in range(1,m+1): d[0][i]=i for i in range(1, n+1): for j in range(1, m+1): # 문자가 같다면, 왼쪽 위의 수를 그대로 대입 if str1[i-1]==str2[j-1]: d[i][j]=d[i-1][j-1] # 문자가 다르다면, 3가지 경우 중에서 최솟값 찾기 else: d[i][j]=1+min(d[i][j-1], d[i-1][j], d[i-1][j-1]) print(d[n][m]) 삽입 : 왼쪽 + 1 삭제 : 위쪽 +.. 2021. 2. 22. 못생긴 수 p. 381 n=int(input()) i2=i3=i5=0 next2=2 next3=3 next5=5 d=[0]*n d[0]=1 for i in range(1,n): d[i]=min(next2,next3,next5) if d[i]==next2: i2+=1 next2=d[i2]*2 if d[i]==next3: i3+=1 next3=d[i3]*3 if d[i]==next5: i5+=1 next5=d[i5]*3 print(d[n-1]) 2021. 2. 22. 병사 배치하기 p. 380 n=int(input()) array=list(map(int, input().split())) array.reverse() d=[1]*n for i in range(1,n): for j in range(0,i): if array[j] 2021. 2. 22. 퇴사 p. 377 n=int(input()) t=[] p=[] dp=[0]*(n+1) max_value=0 for i in range(n): _t,_p=map(int, input().split()) t.append(_t) p.append(_p) for i in range(n-1,-1,-1): day=i+t[i] if day 2021. 2. 22. 정수 삼각형 p. 376 n=int(input()) d=[] for i in range(n): d.append(list(map(int, input().split()))) for i in range(1,n): for j in range(len(d[i])): # 왼쪽 if j == 0: left=0 else: left=d[i-1][j-1] # 오른쪽 if j==i: right=0 else: right=d[i-1][j] d[i][j]=d[i][j]+max(left, right) print(max(d[n-1])) 2021. 2. 22. 금광 p. 375 test_case=int(input()) tc_result=[] for _ in range(test_case): n,m=map(int, input().split()) array=list(map(int, input().split())) d=[] index=0 for i in range(n): d.append(array[index:index+m]) index += m for j in range(1, m): for i in range(n): # 왼쪽 위에서 오는 경우 if i==0: left_up=0 else: left_up=d[i-1][j-1] # 왼쪽에서 오는 경우 left=d[i][j-1] # 왼쪽 아래에서 오는 경우 if i==n-1: left_down=0 else: left_down=d[.. 2021. 2. 22. 이전 1 2 다음