yeony's story

dfs만을 이용하면 시간초과가 나는 문제 다이나믹 프로그래밍을 이용해야 한다. 이중 for문으로 탐색을 진행한다. 오른쪽, 아래로만 이동가능하며 dp[n-1][n-1]에 경로의 수가 저장되어 있다. N=int(input()) array=[list(map(int,input().split())) for _ in range(N)] # 오른쪽이나 아래로만 이동 가능 # 0이 종착점 answer=0 dp=[[0]*N for _ in range(N)] dp[0][0]=1 for i in range(N): for j in range(N): if i == N - 1 and j == N - 1: # 끝에 도달했을 때 print(dp[i][j]) break cnt = array[i][j] # 오른쪽으로 가기 if j + ..

https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net 처음엔 함수를 만들어서 하려고 했는데 굳이 그렇게 할 필요 없을 것 같아서 (사실 재귀함수보다 반복문이 더 편함..) 반복문을 사용하여 다이나믹 프로그래밍 기법으로 문제를 해결했다! t = int(input()) array = [0 for _ in range(68)] array[0] = 1 array[1] = 1 array[2] = 2 array[3] = 4 for _ in ..

dp는 항상 어렵다 ^^... →, ↓의 두 방향으로 움직일 수 있을 때 (1,1)에서 (n,m)까지 도달하는 경우의 수는 dp[x][y]= dp[x-1][y] + dp[x][y-1] 해결할 수도 있다. →, ↓, ↘의 세 방향으로 움직일 수 있을 때, (1,1)에서 (n,m)까지 도달하는 경우의 수는 dp[x][y]= dp[x-1][y] + dp[x][y-1] + dp[x-1][y-1] 위 점화식을 이용하여 구할 수 있다. 즉 갈 수 있는 방향에 따라 더해지는 인수가 달라지는 것을 유의하기 dp[1][1]에 1을 넣어서 초기화한 후 해당 점화식을 실행시킨다. n=3, m=2이면 0 0 0 0 1 1 0 1 3 0 1 5 n, m = map(int, input().split()) dp = [[0 for ..

다이나믹 프로그래밍 기법을 사용하여 푸는 피보나치 수열 문제 시간은 68 ms 나옴! n이 3 이하면 1을 출력하고 프로그램 종료 n이 4 이상이면 피보나치 수열 기법을 적용한다. n = int(input()) if n < 4: print(1) exit() else: f = [0 for _ in range(n + 1)] for i in range(1, 4): f[i] = 1 for i in range(4,n+1): f[i]=f[i-1]+f[i-3] print(f[n]) 코드 양을 좀 줄여봄! 배열의 크기를 미리 주어진 최대 크기만큼 잡아주고 시작함! 그러면 for문을 덜 돌려도 되고 if else문을 쓸 필요가 없음! f = [0 for _ in range(117)] f[1], f[2], f[3] = 1..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 정사각형을 찾으려면 다이나믹 프로그래밍을 사용해야 한다. ** 정사각형 변의 길이를 구하는 방법 ** 1. 해당 칸이 1로 채워져있어야 한다. 2. array[i-1][j], array[i][j-1], array[i-1][j-1] 중에서 가장 작은 값을 array[i][j]와 더해서 array[i][j]의 값을 갱신한다. >> 정사각형이 되려면 현재 위치를 기준으로 한칸 위(i-1, j), 왼쪽으로 한칸 옆(i,j-1), 대각선 기준으로 왼쪽 위 (i-1, j-1)이..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이렇게 보면 일정한 규칙들을 찾아낼 수 있었다. 표로 정리해보니 아래와 같이 나왔고 다이나믹 프로그래밍을 사용하면 손쉽게 값을 구해낼 수 있었다. ''' 조건 1. 덧셈의 순서가 바뀐 경우 > 다른 경우로 센다. 조건 2. 한 개의 수를 여러번 쓸 수 있다. 출력 : 1000000000으로 나눈 나머지를 출력한다. ''' n, k = map(int, input().split()) array = [i for i in range(0, n + 1)] dp = [[0 for _ in range(n)] for _ in range(k..

다이나믹 프로그래밍 문제! 경우의 수를 따져서 출력해야 하는데 n=1, n=2까지 직접 경우의 수를 따져보며 규칙을 발견하며 푸는 방식 n=0일땐 1 사자가 하나도 배치가 되어있지 않은 경우의 수도 하나의 경우로 친다고 했으므로. n=1일땐 3 oo, xo, ox 총 3가지 n=2일땐 7 1) n번째 줄이 모두 비어있는 상태 (oo) n=1 oo. xo. ox n=2 oo oo. oo -> 3가지 dp[n-1] * 1 : n번째 줄에는 oo 하나의 경우만 존재하고 있으므로 1를 곱하는 것 2) n-1번째 줄이 모두 비어있는 경우 (oo) n=1 oo. oo n=2 xo ox -> 2가지 dp[n-2] * 2 3) n-1, n번째 줄이 모두 채워져 있는 경우 (ox , xo) dp[n-1]-dp[n-2] ..

dp를 이용하여 푸는 문제 dp 할 때는 n+1, m+1의 배열로 만든다. 그래야 인덱스 처리를 따로 해주지 않아도 에러가 나지 않는다 :) array 배열 0 0 0 0 0 0 1 2 3 4 0 0 0 0 5 0 9 8 7 6 0 0 0 0 0 dp 배열 0 0 0 0 0 0 1+0 = 1 2+1 = 3 3+3 = 6 4+6 = 10 0 0+1= 1 0+3 = 3 0+6= 6 5+10=15 0 9+1=10 8+10=18 7+18=25 6+25=31 0 0 0 0 0 n, m = map(int, input().split()) array = [list(map(int, input().split())) for _ in range(n)] dp = [[0 for _ in range(m+1)] for _ in ra..

역시나 처음에 조합부터 떠오른 1인.. 하지만 시간 초과 뜰 게 뻔해서 dp로 다시 방향을 바꾸었다! 이 문제는 피보나치 수열과 매우 유사하다. n=1일때 1개 n=2일때 2개 n=3일때 3개 (1+2) n=4일때 5개 (2+3) dp[n]=dp[n-1]+dp[n-2] 그래서 간단하게 답을 도출해낼 수 있었다. 정답코드는 아래와 같다 n=int(input()) dp=[0] * 1000001 dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=(dp[i-1]+dp[i-2])%15746 print(dp[n]) 위 코드 같은 경우에는 시간이 473ms가 떠서 더 좋은 방식이 있나 찾아봤더니 행렬곱셈을 이용하여 피보나치 수열을 하게 되면 더 빠르게 값이 도출된다는 것을 알게 되었다...

dp = [1, 1, 1, 2] t = int(input()) for i in range(t): n = int(input()) if len(dp) < n: for _ in range(n - len(dp)): dp.append(dp[len(dp) - 3] + dp[len(dp) - 2]) print(dp[n - 1]) continue # 이미 값이 정해져있는 경우 print(dp[n - 1])