전체 글

제곱수의 합 풀이

문제 링크: https://www.acmicpc.net/problem/1699 백준 알고리즘 기초 1/2 400에서 13번째 - 1699번 제곱수의 합을 풀어보았다. 풀이: 코드는 https://lakelouise.tistory.com/61를 참고했고, dp는 계속 해도 어려운 거 같다. C++ Python n=int(input()) dp=[i for i in range(n+1)] for i in range(1,n+1): for j in range(1,i): if j**2>i: break if dp[i]>dp[i-j**2]+1: dp[i]=dp[i-j**2]+1 print(dp[n]) Java

연속합 풀이

문제 링크: https://www.acmicpc.net/problem/1912 백준 알고리즘 기초 1/2 400에서 12번째 - 1912번 연속합을 풀어보았다. 풀이: 동적 계획법은 현재 상태와 전 상태를 비교하는 과정이 정말 중요한 거 같다. C++ Python n=int(input()) arr=list(map(int,input().split())) dp=[arr[i] for i in range(n)] for i in range(1,n): dp[i]=max(dp[i],dp[i-1]+dp[i]) print(max(dp)) Java

가장 긴 증가하는 부분 수열 4 풀이

문제 링크: https://www.acmicpc.net/problem/14002 백준 알고리즘 기초 1/2 400에서 11번째 - 14002번 가장 긴 증가하는 부분 수열 4를 풀어보았다. 풀이: 가장 긴 증가하는 부분 수열의 길이와 그 수열을 출력하는 문제이다. 파이썬의 경우, 수열을 출력하는 부분을 수열의 길이와 같이 하고자 했으나, 다른 사람들의 풀이를 참고해 분리했다. C++ Python n=int(input()) arr=list(map(int,input().split())) dp=[1 for i in range(1001)] for i in range(1,n): for j in range(0,i): if arr[j]

가장 긴 증가하는 부분 수열 풀이

문제 링크: https://www.acmicpc.net/problem/11053 백준 알고리즘 기초 1/2 400에서 10번째 - 11053번 가장 긴 증가하는 부분 수열을 풀어보았다. 풀이: LIS의 이해가 필요하다. https://techblog-history-younghunjo1.tistory.com/295 와 https://youtu.be/CE2b_-XfVDk 를 보면 이해가 될 것이다. C++ Python n=int(input()) arr=list(map(int,input().split())) dp=[1 for i in range(1001)] for i in range(1,n): for j in range(0,i): if arr[j]

이친수 풀이

문제 링크: https://www.acmicpc.net/problem/2193 백준 알고리즘 기초 1/2 400에서 9번째 - 2193번 이친수를 풀어보았다. 풀이: dp[i]=dp[i-1]+dp[i-2]라는 점화식을 이용한다. C++ Python dp=[0 for i in range(91)] dp[1]=1 dp[2]=1 n=int(input()) for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]) Java

쉬운 계단 수 풀이

문제 링크: https://www.acmicpc.net/problem/10844 백준 알고리즘 기초 1/2 400에서 8번째 - 10844번 쉬운 계단 수를 풀어보았다. 풀이: dp를 2차원 배열로 만들고, 어떤 수로 시작하는지를 나누어 점화식을 세워야 한다. C++ Python dp=[[0 for i in range(10)] for j in range(101)] for i in range(1,10): # 1자리수 dp[1][i]=1 n=int(input()) for i in range(2,n+1): for j in range(10): if j==0: dp[i][j]=dp[i-1][1] # 0으로 시작 elif j==9: dp[i][j]=dp[i-1][8] # 9로 시작 else: dp[i][j]=dp[..

1, 2, 3 더하기 5 풀이

문제 링크: https://www.acmicpc.net/problem/15990 백준 알고리즘 기초 1/2 400에서 7번째 - 15990번 1, 2, 3 더하기 5를 풀어보았다. 풀이: 규칙 찾기가 매우 힘들었다. 파이썬은 https://ji-gwang.tistory.com/274 이 코드를 참고했다. C++ Python dp=[[0 for i in range(3)]for j in range(100001)] dp[1]=[1,0,0] dp[2]=[0,1,0] dp[3]=[1,1,1] for i in range(4,100001): dp[i][0]=(dp[i-1][1]+dp[i-1][2])%1000000009 dp[i][1]=(dp[i-2][0]+dp[i-2][2])%1000000009 dp[i][2]=(d..

카드 구매하기 2 풀이

문제 링크: https://www.acmicpc.net/problem/16194 백준 알고리즘 기초 1/2 400에서 6번째 - 16194번 카드 구매하기 2를 풀어보았다. 풀이: 점화식은 카드 구매하기 1과 같으나, dp의 처음을 0으로 설정해 주면 된다. C++ Python n=int(input()) p=[0]+list(map(int,input().split())) dp=[100000]*(n+1) dp[0]=0 for i in range(1,n+1): for j in range(1,i+1): dp[i]=min(dp[i],dp[i-j]+p[j]) print(dp[-1]) Java