yeony's story

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..

다이나믹 프로그래밍 문제! 경우의 수를 따져서 출력해야 하는데 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] ..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net (처음 든 생각) 항상 완탐부터 생각난다.... 하지만 딱 떠오르는 생각이 없었다. 아무리 생각해봐도 모르겠어서 인터넷 풀이 검색.. (풀이 : dp) 처음에 input()으로 입력값을 받았는데 시간초과, sys.stdin.readlin() 사용하니까 통과함! 이 문제는 완탐으로 하면 시간초과가 뜬다 연산개수가 150만개라서..! 생각해야 하는 부분 1. 해당 날짜에..