전체 글

정수 삼각형 풀이

문제 링크: https://www.acmicpc.net/problem/1932 백준 알고리즘 기초 1/2 401에서 7번째 - 1932번 정수 삼각형을 풀어보았다. 풀이: 삼각형에서 원소의 위치를 왼쪽 변, 오른쪽 변, 둘 다 아닌 상태 이렇게 세 가지로 분류해야 한다. C++ Python n=int(input()) arr=[] for i in range(n): arr.append(list(map(int,input().split()))) for i in range(1,n): for j in range(i+1): if j==0: arr[i][j]=arr[i][j]+arr[i-1][j] elif j==i: arr[i][j]=arr[i][j]+arr[i-1][j-1] else: arr[i][j]=max(arr..

포도주 시식 풀이

문제 링크: https://www.acmicpc.net/problem/2156 백준 알고리즘 기초 1/2 401에서 6번째 - 2156번 포도주 시식을 풀어보았다. 풀이: https://myjamong.tistory.com/313 코드를 참고했다. C++ Python n=int(input()) arr=[0] dp=[0]*(n+2) for i in range(n): arr.append(int(input())) arr.append(0) dp[1]=arr[1] dp[2]=dp[1]+arr[2] for i in range(3,n+1): dp[i]=max(dp[i-1],dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]) print(dp[n]) Java

스티커 풀이

문제 링크: https://www.acmicpc.net/problem/9465 백준 알고리즘 기초 1/2 401에서 5번째 - 9465번 스티커를 풀어보았다. 풀이: 2차원 점화식을 만들어 그거대로 코드를 짜면 된다. C++ Python t=int(input()) for i in range(t): dp=[] n=int(input()) dp.append(list(map(int,input().split()))) dp.append(list(map(int,input().split()))) for j in range(1,n): if j==1: dp[0][j]+=dp[1][j-1] dp[1][j]+=dp[0][j-1] else: dp[0][j]+=max(dp[1][j-1],dp[1][j-2]) dp[1][j]+=m..

오르막 수 풀이

문제 링크: https://www.acmicpc.net/problem/11057 백준 알고리즘 기초 1/2 401에서 4번째 - 11057번 오르막 수를 풀어보았다. 풀이: dp[i]=dp[i-1]*(i+9)//i 이다 C++ Python n=int(input()) dp=[0 for i in range(n+1)] dp[1]=10 for i in range(2,n+1): dp[i]=dp[i-1]*(i+9)//i print(dp[n]%10007) Java

동물원 풀이

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