본문 바로가기

동적 계획법 1

[백준/C언어] 12865번 - 평범한 배낭 백준 웹사이트 "12865번 - 평범한 배낭" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 소스 코드 #include int max(int a, int b); int main(void){ int N, K; scanf("%d %d", &N, &K); int objects[N][2]; for(int i=0; i 더보기
[백준/C언어] 1912번 - 연속합 백준 웹사이트 "1912번 - 연속합" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 소스 코드 #include int main(void){ int n; scanf("%d", &n); int num[n]; for(int i=0; i 더보기
[백준/C언어] 9251번 - LCS 백준 웹사이트 "9251번 - LCS" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 소스 코드 #include #include int max(int a, int b); int main(void){ char string1 [1001]; char string2 [1001]; scanf("%s", &string1); scanf("%s", &string2); int string1_len = strlen(.. 더보기
[백준/C언어] 2565번 - 전깃줄 백준 웹사이트 "2565번 - 전깃줄" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 소스 코드 #include void sort(int * A, int * B, int num); int max(int a, int b); int main(void){ int num; scanf("%d", &num); int A[num]; int B[num]; for(int i=0; i 더보기
[백준/C언어] 11054번 - 가장 긴 바이토닉 부분 수열 백준 웹사이트 "11054번 - 가장 긴 바이토닉 부분 수열" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 소스 코드 #include int max(int a, int b); int main(void){ int N; scanf("%d", &N); int A[N]; for(int i=0; i 더보기
[백준/C언어] 11053번 - 가장 긴 증가하는 부분 수열 백준 웹사이트 "11053번 - 가장 긴 증가하는 부분 수열" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 소스 코드 #include int max(int a, int b); int main(void){ int N; scanf("%d", &N); int A[N]; for(int i=0; i 더보기
[백준/C언어] 2156번 - 포도주 시식 백준 웹사이트 "2156번 - 포도주 시식" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 소스 코드 #include int max(int a, int b, int c); int main(void){ int n; scanf("%d", &n); int wine[n+1]; for(int i=1; i=2){ quantity[2] = wine[1]+wine[2]; //printf("%d: %d\n", 2, quantity[2]); } for(int j.. 더보기
[백준/C언어] 10844번 - 쉬운 계단 수 백준 웹사이트 "10844번 - 쉬운 계단 수" 문제풀이입니다. 언어는 C언어입니다. (제출 언어: C99) 문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 소스 코드 #include int main(void){ int N; scanf("%d", &N); int stair[N+1][10]; //stair[n][i]: 길이가 n, 마지막 자리가 i인 계단수의 개수 stair[1][0]=0; for(int i=1; i 더보기

티스토리툴바