펭귄삼촌

www.acmicpc.net/problem/12865 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 using namespace std; int n, k; // 물품의 개수, 준서가 버틸 수 있는 무게 int product[101][2]; // 물건의 무게와 가치 배열 int dp[101][100001]; int max(int a, int b){ return a >= b ? a : b; } void solve(){ int ..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 코드 #include using namespace std; int n; int A[1000]; int inc_arr[1000]; int dec_arr[1000]; int len = 0; int max(int a, int b){ return a > b ? a : b; } void init(){ cin >> n; for(int i=0; i> A[i]; } } void solve(){ for(int i=0; i ... SN-1 > SN..

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 코드 #include using namespace std; int n; // 수열 A의 크기. int arr[1000]; // 수열 A를 이루고 있는 Ai. int dp[1000]; // Ai를 마지막 수로 갖는 수열 중 가장 긴 길이. int max_len = 1; // 가장 긴 수열의 길이. int max(int a, int b)..

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 코드 #include using namespace std; int n; int wine[10001]; int dp[10001]; int max(int a, int b){ return a > b ? a : b; } void init(){ cin >> n; for(int i=1; i> wine[i]; } } void solve(){ dp[1] = wine[1]; dp[2] = wine[1] + wine[2]; dp[..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 코드 #include using namespace std; int n; int answer = 0; int stair[10] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}; int dp[10]; void solve(){ for(int i=2; i

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 코드 #include using namespace std; int n; int dp[1000001]; //각 숫자별 1이 될 때까지 수행해야하는 최소 단계 저장. int min(int a, int b){ return a < b ? a : b; } void solve(){ dp[1] = 0; dp[2] = 1; dp[3] = 1; for(int i=4; i n; solve(); return 0; } 문제 동적계획법, 즉 DP를 사용하여 푸는 문제입니다. 주어진 수 N을 3가지 연산을 활용하여 1로 만드는데 연산횟수가 최소로 될..

1932번: 정수 삼각형 링크 코드 #include using namespace std; int n; int tri[500][500]; void init(){ cin >> n; for(int i=0; i tri[i][j]; } } } void solve(){ int max_num = 0; for(int i=1; i max_num) max_num = tri[i][j]; } } cout

1149번: RGB거리 링크 코드 #include using namespace std; // RGB 거리 int rgb[1000][3]; // 집을 색칠하는데 드는 비용 입력 받기 void init(int n){ for(int i=0; i> rgb[i][0] >> rgb[i][1] >> rgb[i][2]; } } void solve(int n){ for(int i=1; i G 순으로 칠해져서 1 + 5 + 1 이 되어야 하지만 N = 2 일때 그 순간의 최소값이 2라는 함정에 빠지게 된 것이다. 따라서 점화식은 R, G, B 에 따른 3개를 운용해야 한다. 변수 int rgb[1000][3]; 집을 칠하는 데 필요한 비용을 담는 배열을 선언한다. rgb[집의 개수][색의 개수] 이후, Input 따라 배..