코테용 문제풀이/백준

동물원 풀이

문제 링크: https://www.acmicpc.net/problem/1309 백준 알고리즘 기초 1/2 401에서 3번째 - 1309번 동물원을 풀어보았다. 풀이: dp[i]=2*dp[i-1]+dp[i-2]라는 점화식을 구해내면 된다. C++ Python n=int(input()) dp=[0 for i in range(n+1)] dp[0]=1 dp[1]=3 for i in range(2,n+1): dp[i]=(2*dp[i-1]+dp[i-2])%9901 print(dp[n]) Java

RGB거리 풀이

문제 링크: https://www.acmicpc.net/problem/1149 백준 알고리즘 기초 1/2 401에서 2번째 - 1149번 RGB거리를 풀어보았다. 풀이: 각 위치와 전단계의 두 위치를 비교한다. C++ Python n=int(input()) dp=[] for i in range(n): dp.append(list(map(int,input().split()))) for i in range(1,n): dp[i][0]=min(dp[i-1][1],dp[i-1][2])+dp[i][0] dp[i][1]=min(dp[i-1][0],dp[i-1][2])+dp[i][1] dp[i][2]=min(dp[i-1][0],dp[i-1][1])+dp[i][2] print(min(dp[n-1][0],dp[n-1][1]..

1, 2, 3 더하기 3 풀이

문제 링크: https://www.acmicpc.net/problem/15988 백준 알고리즘 기초 1/2 401에서 1번째 -15988번 1, 2, 3 더하기 3을 풀어보았다. 풀이: 1, 2, 3 더하기를 푼 코드를 조금 변형만 했다. C++ Python arr=[0]*1000001 arr[1]=1 arr[2]=2 arr[3]=4 for i in range(4,1000001): arr[i]=(arr[i-1]+arr[i-2]+arr[i-3])%1000000009 t=int(input()) for i in range(t): print(arr[int(input())]) Java

합분해 풀이

문제 링크: https://www.acmicpc.net/problem/2225 백준 알고리즘 기초 1/2 400에서 14번째 - 2225번 합분해를 풀어보았다. 풀이: C++ Python n,k=map(int,input().split()) dp=[[0 for i in range(k+1)] for j in range(n+1)] dp[0][0]=1 for i in range(0,n+1): for j in range(1,k+1): dp[i][j]=dp[i][j-1]+dp[i-1][j] print(dp[n][k]%1000000000) Java

제곱수의 합 풀이

문제 링크: 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[..