대엉코딩

www.acmicpc.net/problem/7570

1. 풀이방법

 - 몇가지 예시를 직접 종이에 써서 알아보고, 코드로도 짜보고 하면서 알아낸 것이

 - 순방향(? 증가하는) 쪽의 가장 긴 증가수열의 길이를 알아내는 것이 핵심 이었습니다.

 - 근데 한번의 작업으로 맨 앞 혹은 맨 뒤 양 끝으로만 보낼 수 있기 때문에 그냥 최장증가수열이 아닌 !

 - 1씩 증가하는 최장증가수열의 길이를 구해야 했습니다!!!!

 - 입력의 범위를 보니 이중반복문이 들어갈 경우 시간초과가 명백하여서 dp를 통해서 입력을 받으면서 구했습니다.

2. 주의사항 

 - 지금보면 단순해보이는 numarr[tmp]=numarr[tmp-1]+1 이 것을 생각해내는 게 꽤 어려웠습니다 ㅠㅠㅠ

 - dp에 익숙하지 않아서 일까요...꽤 오래걸렸습니다...

 - 보시는 분들 중에 이해가 안되는 분들은 임의의 길이 7 정도의 입력을 직접 그려보면서 써가면서 하시면 

 - 이해가 잘 되실 것 같습니다.

3. 나의코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;

int N;
int numarr[1000001];
int maxlistcount;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp; 
		numarr[tmp] = numarr[tmp - 1] + 1;
		maxlistcount = max(maxlistcount, numarr[tmp]);
	}
	cout << N - maxlistcount << "\n";
	return 0;
}

www.acmicpc.net/problem/12865

1. 풀이방법

 - 처음에 떠올린 방법은 브루트 포스로 모든 경우의 수 (조합) 을 모두 계산해 보는 것 

 - 이렇게 짜볼까 하다가 시간초과가 매우 발생할 것 같아서 방향을 바꿨습니다.

 - 그냥 메모리를 사용해서 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블을 선언하자 라고 생각.

 - N개의 물건들을 하나씩 살펴 보면서 버틸 수 있는 무게 K 밑으로 살펴보며 이 물건을 넣어가며 테이블을 갱신

2. 주의사항

 - 아직 알고리즘 문제풀이가 많이 부족해서 기존의 떠오른 생각 방향에서 다른 쪽으로 생각하는게 부족...

 - 열심히 풀어야겠습니다...

3. 나의코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;

int N, K;
int dp[100001]; // 버틸 수 있는 무게 별로 최대가치를 저장하는 테이블
int weightarr[101];
int valuearr[101];

void dypro() {
	for (int i = 1; i <= N; i++) {
		for (int j =K; j >= 0; j--) {
			if (weightarr[i]<= j) {
				dp[j] = max(dp[j], dp[j- weightarr[i]] + valuearr[i]);
			}
		}
	}
	cout << dp[K] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> weightarr[i] >> valuearr[i];
	}
	dypro();
	return 0;
}

https://www.acmicpc.net/problem/1932

- 삼각형의 위에서 부터 길을 만들어 각 수 를 더하였을 때 가장 큰 값이 되도록 하는 길을 쫓아가서

- 그 값을 출력하는 문제입니다.

- vector 두개를 이용하여 들어오는 값과 vector 0과 들어오는 값을 비교하여 vector 1에 저장하고

- 그다음 들어오는 값들은 vector 1과 들어오는 값들을 비교하고 더해 vector 0에 저장하는 작업을 반복한 후

- 물론 작업이 끝난 배열은 초기화를 해야 합니다 (그 다음 줄에서 넣어야하므로)

- 마지막에 n의 값에 따라서 vector 0 또는 vector 1 을 내림차순 으로 정렬 한후 index 0의 값을 출력하였습니다.

- 값을 더하고 저장하고 더하고 저장하고 를 반복하는 작업이라고 생각 하시면 될거 같습니다.

- 그리고 각 입력의 처음과 마지막은 비교를 할 필요없이 바로 0번쨰 index그리고 마지막 index랑 더해서 넣으면 됩니다.

<필기>

<코드>

https://www.acmicpc.net/problem/2579

다이나믹 프로그래밍을 이용하였습니다.

조건3개를 잘 파악한 후 고민을 좀 했는데

2번째 문제 조건을 잘 이용해야 했습니다.

목표계단을 무조건 밟아야 한다는 가정하에(조건3)

두가지 경우의 수가 나옵니다 (조건1)

1) 바로 전계단을 밟고 목표계단을 밟는경우

2) 전전계단을 밟고 목표계단을 밟는 경우

하지만 1번 조건을 그대로 적용할 경우 3번연속된 계단을 밟게 되는 경우가 생길수 있습니다.(즉 조건2 를 무시한 상태)

즉 전계단을 밟기전에는 전전전계단을 밟았어야 한다는 조건이 들어가야 합니다.(조건추가)

dp는 최대값을 저장한 배열이고 stairvalue는 각 계단의 값을 넣어놓은 배열 입니다.

<필기>

<코드>

https://www.acmicpc.net/problem/9095

간단한 다이나믹 프로그래밍 문제라고 할수 있겠습니다.

사실 처음 할때 개념을 이해하기가 꽤 힘들었던 것 같았던 기억이 있습니다....

이번에 아이패드를 사면서 사용하면서 풀고 있는데 보면서 약간 이해를 도울 수 있었으면 좋겠네요

목표지점 n으로 가기 위해 정수 123만 사용할수 있기 때문에

4이상의 숫자들은  1칸 가고 목표지점에 가는 경우의 수 dp[n-1]

                        2칸 가고 목표지점에 가는 경우의 수 dp[n-2]

                        3칸 가고 목표지점에 가는 경우의 수 dp[n-3]

으로 이해하시면 편하지 않을까 생각합니다.

<필기>

<코드>