dp2 1463.1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이게 왜 DP 인지 생각하다가 DP처럼 재귀를 사용하니까 풀렸다 경우의 수를 구하면 한번 내려갈때마다 3을 곱해서 3의 제곱 형태지만 재귀를 사용하면 메모라이즈 해당칸의 값은 기억하고 있어서 다시 계산할 필요가 없다 대표적으로 피보나치 수열에서 사용하는 방식과 동일하다 각각 3가지 경우로 나눠서 값을 찾아가면 된다 def f(x): if x==1: return 0 a=b=c=40 if x%3==0: if t[x//3]: c=t[x//3] else: c=f(x//3) if x%2==0 : if t[x//2]: b.. 2023. 5. 30. DP 다이나믹 프로그래밍 중 하나 리스트의 값이 점점 커지기 떄문에 답이 나머지를 출력하는거라면 중간에 계속 나눠준다 수의 크기가 작아지기 때문에 그게 더 빠르다 더하기라서 가능 곱하기면 더 큰수로 나눠야함 n1=1000000 a=[0]*n1 b=[0]*n1 c=[0]*n1 c1=[0]*n1 c2=[0]*n1 c3=[0]*n1 a[0]=c[0]=b[0]=c2[0]=1 mi=10**7 for n in range(1,n1): a[n]=(a[n-1]+b[n-1]+c[n-1])%mi b[n]=(b[n-1]+c2[n-1])%mi c3[n]=(c2[n-2]-c3[n-1])%mi c2[n]=(b[n]-c3[n])%mi c1[n]=(c[n-2]-c1[n-1])%mi c[n]=(a[n]-c1[n])%mi #a[n-3]=b[n.. 2023. 5. 28. 이전 1 다음