[백준] 1932번 정수 삼각형 (C)

#include using namespace std; int in[501][501]; int dp[501][501]; int main(){ int n; cin>>n; int ans=0; for(int i=1;iin[i][j]; dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+in[i][j]; ans=max(ans,dp[i][j]); } } cout

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 29.
• textsms

[백준] 1149번 RGB거리

문제 주소 백준 1149번 RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 알고리즘 DP 힌트 배열에 각 집에서 각각의 색을 칠하는데 최소 비용을 저장한다. 문제 풀이 dp배열은 그 집에서 각 색을 칠할때의 최소 비용을 저장하는 배열이다. RGB를 각각 012원소에 넣고 i번째 집에서 0번째 색을 칠하기 위한 최소 비용은 i-1번째 집에서 1 또는 2를 칠하기 위한 최소 비용중 작은 값에 cost[i][0]을 더한 값이다. #include using names..

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 28.
• textsms

[백준] 9461번 파도반 수열 (C)

문제 출처 ICPC Asia Pacific Korea Asia Regional - Daejeon 2013 G번 문제 주소 백준 9461번 파도반 수열 9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하 www.acmicpc.net 알고리즘 DP 힌트 n번째 삼각형 변의 길이와 이..

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 28.
• textsms

[백준] 1904번 01타일 (C)

#include using namespace std; int dp[1000001]; int main(){ int n; cin>>n; dp[1]=1; dp[2]=2; for(int i=3;i

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 28.
• textsms

[백준] 1003번 피보나치 함수

문제 주소 백준 1003번 피보나치 함수 알고리즘 DP 힌트 피보나치 수열의 각 원소의 0과 1의 개수도 피보나치 수열이다. 문제 풀이 #include using namespace std; int cnt1, cnt0; int dp[50][2]; int main(){ dp[0][0]=1; dp[1][1]=1; for(int i=2;i>n; for(int i=0;i>tmp; cout

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 28.
• textsms

[백준] 2748번 피보나치 수2 (C)

문제 주소 백준 2748번 피보나치 수2 C 백준 2748번: 피보나치 수2 https://www.acmicpc.net/problem/2748 메모리 제약 사항이 128 MB 임으로 메모제이션이나 다이나믹프로그래밍으로 접근 해야 한다. 키워드 - 정수론, 피보나치, 다이나믹 프로그래밍 1 2 3 5 8 13 21 이전 요소.. bitwise.tistory.com 알고리즘 DP 힌트 피보나치 수들을 배열에 저장한다. 문제 풀이 피보나치 수열을 배열에 저장하여 n번째 수까지 구한다. #include using namespace std; long long int p[100]; int main(){ int n; cin>>n; p[1]=1LL; p[0]=0LL; for(int i=2;i

• format_list_bulleted Problem Solve/Dynamic Programming
• · 2020. 3. 28.
• textsms