RUBY

출처:: www.acmicpc.net/problem/10164 분류:: dp 1. 문제 이해 및 해결과정 - k가 0이 아니라면, 빨간 네모의 경우와 파란네모의 경우를 찾아 각각 곱해주면 되는데 - 파란 네모의 경우는 번호(8)를 기준으로 다시 초기화되어서 dp배열을 만들게 되므로 곧 다시 빨간 네모dp테이블과 같다 2. 풀이방법 1.dp #격자상의 경로 #https://www.acmicpc.net/problem/10164 import sys sys.stdin = open("input.txt","r") n,m,k=map(int,input().split()) dp=[[0]*(m+1) for _ in range(n+1)] dp[0][1]=1 cnt=1 for i in range(1,n+1): for j in..

출처:: www.acmicpc.net/problem/1789 분류:: 1. 문제 이해 및 해결과정 2. 풀이방법 1. #수들의 합 #https://www.acmicpc.net/problem/1789 import sys sys.stdin = open("input.txt","r") n=int(input()) #x(x+1)/2 = n x=1 while(x*(x+1)/2 n: break num+=1 print(cnt-1) 3. 오답원인 4. 알게된 점

출처:: www.acmicpc.net/problem/2294 분류:: dp 1. 문제 이해 및 해결과정 - 문제 예시의 경우, dp[i - 1], dp[i - 5], dp[i - 12] 중 min값에 1을 더하면 된다 - dp[0]=0 2. 풀이방법 1. dp #동전2 #https://www.acmicpc.net/problem/2294 import sys sys.stdin = open("input.txt","r") n,k=map(int,input().split()) coin = [ int(input()) for _ in range(n)] INF=100001 #INF라면 만들수 없는 숫자 dp=[INF]*(INF) dp[0]=0 #꼭 필요, 0원을 만들 수 있는 방법은 0개 coin.sort() for i..

출처:: https://www.acmicpc.net/problem/1463 분류 ::: dp 1. 문제 이해 및 해결과정 2. 풀이방법 1. DP(dynamic programming) -bottomup #1로 만들기 #https://www.acmicpc.net/problem/1463 import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*(n+1) for i in range(2,n+1): #1뺴는 경우 dp[i]=dp[i-1]+1 #2로 나누어 떨어지는 경우 if i%2==0: dp[i]=min(dp[i],dp[i//2]+1) #3으로 나누어 떨어지는 경우 if i%3==0: dp[i]=min(dp[i],dp[i//3]+1) print(dp..

출처:: www.acmicpc.net/problem/14620 분류:: dfs 1. 문제 이해 및 해결과정 - 모든 경우 탐색 dfs - 가능한 열매 시작점은 1~n-2,1~n-2 까지임 - 아직 선택되지 않은 열매라면, 현재 열매에서 꽃잎까지 비용모두 저장하고(cost), sum(기존값)에 더해준다 - 선택되었던 것을 취소 - cnt==3 (모두선택되면), 가능한 값들 중 최소값 저장 2. 풀이방법 1. dfs #꽃길 #https://www.acmicpc.net/problem/14620 import sys sys.stdin = open("input.txt","r") n=int(input()) board=[list(map(int,input().split())) for _ in range(n)] #가격 v..

출처:: www.acmicpc.net/problem/1753 분류:: 다익스트라 1. 문제 이해 및 해결과정 2. 풀이방법 1. 다익스트라 #최단경로 #https://www.acmicpc.net/problem/1753 import sys import heapq sys.stdin = open("input.txt","r") input=sys.stdin.readline v,e=map(int,input().split()) #정점의 개수, 간선의 개수 start=int(input()) graph = [[] for _ in range(v+1)] visited = [False]*(v+1) INF=1e9 dist=[INF]*(v+1) for _ in range(e): a,b,c=map(int,input().split(..

출처:: www.acmicpc.net/problem/14719 분류:: 1. 문제 이해 및 해결과정 - 담기는 물의 양을 계산해서 더한다 - 물이 담기기 위해서는 현재보다 양 쪽의 블럭보다 낮아야한다. 2. 풀이방법 #빗물 #https://www.acmicpc.net/problem/14719 import sys sys.stdin = open("input.txt","r") h,w=map(int,input().split()) block=list(map(int,input().split())) rain=0 for i in range(len(block)): topleft=max(block[:i+1]) # 현재를 기준으로 왼쪽에서 가장 높은 블록 topright=max(block[i:]) # 현재를 기준으로 오른쪽..

출처:: www.acmicpc.net/problem/1806 분류:: 구간 합(prefix sum) , 투포인터 1. 문제 이해 및 해결과정 5 10 1 2 3 4 5 # 3,4,5(12) => 3 10 10 1 1 1 1 1 1 1 1 1 10 # 10 -> 1 2. 풀이방법 1. python 투포인터 #부분합 #https://www.acmicpc.net/problem/1806 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) #n,목표 arr=list(map(int,input().split())) s,e=0,0 sum=0 sol=1e9 tmp=0 for s in range(n): while e=m: #부분합의 차이가 m..