RUBY

출처:: https://www.acmicpc.net/problem/15990 1. 문제 이해 및 해결과정 - dp 2차원 배열로 풀어야 한다. # 1은 하나 작은 수에서 2로 끝나는 것과 3으로 끝나는 것에 붙일 수 있음 dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % d # 2는 둘 작은 수에서 1로 끝나는 것과 3으로 끝나는 것에 붙일 수 있음 dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % d # 3는 셋 작은 수에서 1로 끝나는 것과 2으로 끝나는 것에 붙일 수 있음 dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % d 2. 풀이방법 1. DP #1, 2, 3 더하기 5 #https://www.acmicpc.net..

출처:: https://www.acmicpc.net/problem/15988 1. 문제 이해 및 해결과정 - 1,2,3 더하기 에서 범위가 바뀐 문제이다. - 중간에 %100000~9 를 안해주면 메모리 초과가 난다. 2. 풀이방법 1. DP #1, 2, 3 더하기 3 #https://www.acmicpc.net/problem/15988 import sys t=int(input()) for _ in range(t): n=int(input()) dp=[0]*1000002 dp[1] = 1 dp[2] = 2 dp[3] = 4 if n>=4: for i in range(4,n+1): dp[i]=(dp[i-1]+dp[i-2]+dp[i-3])%1000000009 print(dp[n]%1000000009) 2. D..

출처:: https://www.acmicpc.net/problem/11727 분류:: dp 1. 문제 이해 및 해결과정 2. 풀이방법 1.DP #2×n 타일링 2 #https://www.acmicpc.net/problem/11727 import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*1001 dp[1]=1 dp[2]=3 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2]*2 print(dp[n]%10007) 3. 오답원인 4. 알게된 점

출처:: https://www.acmicpc.net/problem/11726 1. 문제 이해 및 해결과정 2. 풀이방법 1. DP #2×n 타일링 #https://www.acmicpc.net/problem/11726 import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*1001 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]%10007) 3. 오답원인 4. 알게된 점

출처:: https://www.acmicpc.net/problem/9095 1. 문제 이해 및 해결과정 2. 풀이방법 1. DP #1, 2, 3 더하기 #https://www.acmicpc.net/problem/9095 import sys sys.stdin = open("input.txt","r") t=int(input()) for _ in range(t): n=int(input()) #dp=[0]*(n+1) ->에러원인 dp=[0]*12 dp[1]=1 dp[2]=2 dp[3]=4 if n>=4: for i in range(4,n+1): dp[i]=dp[i-1]+dp[i-2]+dp[i-3] print(dp[n]) 2. DP 리팩토링 #1, 2, 3 더하기 #https://www.acmicpc.net/pr..

출처:: https://www.acmicpc.net/problem/11053 1. 문제 이해 및 해결과정 2. 풀이방법 1. LIS #가장 긴 증가하는 부분 수열 #https://www.acmicpc.net/problem/11053 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=list(map(int,input().split())) arr.insert(0,0) dp=[0]*(n+1) dp[1]=1 res=1 for i in range(2,n+1): # 1다음수부터 찾으려는 값까지 max=0 for j in range(i-1,0,-1): #내 앞의 수 까지 최대값 찾기 if arr[i]>arr[j] and dp[j]>max: max=dp[..

출처:: https://www.acmicpc.net/problem/1261 1. 문제 이해 및 해결과정 - Floodfill 대로 BFS를 쓰되, 최단거리를 저장할 때 0이면 거리가 0더해지고 1이면 1더하면 최적의 경로에 1의 개수가 몇개인지 구할 수 있다. - 우선순위를 높이기 위해서 0이라면 왼쪽으로 append하여 우선순위를 높였다. -입력이 붙어있을 때 아래코드로 하면된다. board = [list(map(int, input())) for _ in range(n)] #붙어있는 입력 받기 : input=sys.stdin.readline 때문에 오류가 났었다. 입력이 붙어있을경우, 이 코드를 쓰면 안된다. 2. 풀이방법 1. 가중치가 다른 BFS #알고스팟 #https://www.acmicpc.ne..

출처:: https://www.acmicpc.net/problem/13913 1. 문제 이해 및 해결과정 - 최적의 이동경로까지 출력해야한다. - path[다음위치] = cur(현재) , path에 방문했던 위치를 저장한다. - k에 도착하면 backtracking 해서 출발위치까지 p 에 최적 이동경로를 저장한다. - p는 backtracking 한 것이므로 출발위치 추가해서 reverse해야한다. - if cur==k: print(time[cur]) p=[] print(path) while cur!=n: p.append(cur) cur=path[cur] print(p) 2. 풀이방법 1. BFS #숨바꼭질4 #https://www.acmicpc.net/problem/13913 import sys fr..