전체 글

https://www.acmicpc.net/problem/11727import syssys.stdin = open("input.txt")n = int(sys.stdin.readline().rstrip())dp = [0] * 1001dp[1] = 1dp[2] = 3for i in range(3, n+1): dp[i] = (dp[i-1] + dp[i-2]*2) % 10007print(dp[n]) 알고리즘 분류:- 다이나믹 프로그래밍 Key Points는 없고 그냥 2xn 타일링 풀다가 하나 더 있길래 풀어보았다. 이 문제도 직접 점화식을 찾아서 푸는게 원리 따지는 것보다 더 빠른 것 같다.

https://www.acmicpc.net/problem/11726import sys sys.stdin = open("input.txt")n = int(sys.stdin.readline().rstrip())dp = [0] * 1001dp[1] = 1dp[2] = 2for i in range(3, n+1): dp[i] = (dp[i-1]+ dp[i-2]) % 10007print(dp[n]) 알고리즘 분류:- 다이나믹 프로그래밍 Key Points:직접 케이스 별 값을 찾은 다음 점화식을 세워봤더니 dp[i] = dp[i-1] + dp[i-2]가 나왔다. 조금 더 원리적으로 파고 들어가면 왜 이런 점화식이 도출되는지 알 수 있겠지만 사실 이런 문제는 그냥 직접 점화식을 찾고 넘어가는게 정신 건강에 좋을..

https://www.acmicpc.net/problem/2156import syssys.stdin = open("input.txt")n = int(sys.stdin.readline().rstrip())wine = []for _ in range(n): wine.append(int(sys.stdin.readline().rstrip()))dp = [0] * (n+1)dp[0] = wine[0]if n > 1: dp[1] = wine[0] + wine[1]if n > 2: dp[2] = max(wine[0]+wine[1], wine[1]+wine[2], wine[0]+wine[2])for i in range(3, n): dp[i] = max( dp[i-2] + wine[i],..

https://www.acmicpc.net/problem/1912import syssys.stdin = open("input.txt")n = int(sys.stdin.readline().rstrip())dp = list(map(int, sys.stdin.readline().split()))for i in range(1, n): dp[i] = max(dp[i], dp[i-1]+dp[i])print(max(dp)) 알고리즘 분류:처음에는 누적합 문제인 줄 알고 투포인터 알고리즘으로 풀었더니 시간 초과가 발생했다. DP 유형이라고 생각하기까지가 조금 까다로웠는데, 일단 문제에서 가장 중요한 부분은 연속된 몇 개의 수로 합을 구성한다는 것이다. 중간 중간 음수가 섞여있어도 뭐가 됐든 그 음수 너머에 합을 ..

https://www.acmicpc.net/problem/9095import syssys.stdin = open("input.txt")t = int(sys.stdin.readline().rstrip())for testcase in range(t): dp = [0] * 11 dp[1] = 1 dp[2] = 2 dp[3] = 4 n = int(sys.stdin.readline().rstrip()) for i in range(4, n+1): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] print(dp[n]) 알고리즘 분류:- 다이나믹 프로그래밍 Key Points:원리를 따지는 것보다 어쩌면 각 수에 대한 경우의 수를 계산해서 직접 점화식을..

https://www.acmicpc.net/problem/1463import syssys.stdin = open("input.txt")x = int(sys.stdin.readline().rstrip())dp = [0] * 1000001for i in range(2, x+1): dp[i] = dp[i-1]+1 if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1) if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1)print(dp[x]) 알고리즘 분류:- 다이나믹 프로그래밍 Key Points:dp 문제의 가장 기본이라고 할 수 있는 '1로 만들기' 유형이다. 일단 문제를 읽어보면 세 가지 연산을 할 수 있는데..